알고리즘 : SAT 솔루션 수를 찾는 방법은 무엇입니까?

변수의 수 N과 절 수 K가 같다고 가정합니다. 절을 만족시키는 다양한 방법의 수를 반환하는 알고리즘을 찾으십시오.알고리즘 : SAT 솔루션 수를 찾는 방법은 무엇입니까?

나는 SAT가 독립 세트와 관련이 있다고 읽었습니다.

2017-01-29 jas7

이 숙제가 있습니까? –

@ GeorgSchölly 아니요, 숙제가 아닙니다. 나는 인터뷰 준비를위한 알고리즘을 배우고있다. – jas7

이것은 #P (https://en.wikipedia.org/wiki/Sharp-P?)에 해당합니까? 변수 개수가 절 수와 동일하다는 것을 알고 있습니다. 변수보다 절. 그러나 (X | Y | Z | ...)와 같은 절을 추가하여 거의 변수가없는 문제를 추가 할 수 있습니다. 여기서 X, Y, Z ...는 이전에 사용되지 않은 변수입니다. – mcdowella

N 변수의 함수는 truth-table이고 2^N 행입니다. 각 행은 해결책이 될 수도 있고 그렇지 않을 수도있는 하나의 minterm에 해당합니다.

N이있는 절에는 솔루션의 일부로 minterm 중 하나가 정확하게 제외됩니다. 그것은 절의 모든 거꾸로 된 변수로 구성된 minterm입니다. 제공자

는 K 절은

솔루션의 개수가 N 2^모두 다르다 - K

예 :

K=3 절과 N=3 변수 :

,451,515,

A or B or C 
!A or B or C 
A or B or !C

진실 테이블 세의 입력 : 가능한 팔 개 용어의

A B C output 
0 0 0 0   // excluded by A or B or C 
0 0 1 0   // excluded by A or B or !C 
0 1 0 1 
0 1 1 1 
1 0 0 0   // excluded by !A or B or C  
1 0 1 1 
1 1 0 1 
1 1 1 1

다섯 사실이 남아있다. 따라서 예제에는 2^3 - 3 = 5 개의 해가 있습니다.

출처

2017-01-29 10:09:37

알고리즘 : SAT 솔루션 수를 찾는 방법은 무엇입니까?

답변

관련 문제