독특한 1-in-3 Sat.

Question

크기 2와 3의 클로스가있는 CNF 공식이 있다고 가정합니다. 독특한 만족 과정이 있습니다.

이진 곱셈 회로로 만들어 졌기 때문에 고유 한 할당의 각 비트의 값을 알고 있습니다. 여기서 S는 A * B= s가 Semiprime 번호 인 a * b= s를 곱한 것입니다. 나는!= 1, b!= 1 및 <= b의 조건을 추가 한 다음 수식에 S 값을 추가하여 할당이 고유한지 확인합니다. 공식을 만족시키는 유일한 방법은 입력 비트에서 A와 B의 값을 올바른 순서로 올바른 순서로 두는 것입니다.

각 절의 진정한 리터럴의 수는 1, 2 또는 3입니다. 각 비트의 값을 알고 있기 때문에 각 절에서 어떤 리터럴이 true인지를 정확히 알 수 있고 계산할 수 있습니다. 예를 들어, 나는 정확히 1 개의 리터럴에 의해 어떤 조항을 만족 시키는지 압니다. 그 리터럴은 논리적으로 독특한 솔루션의 일부입니다.

내 질문은 간단합니다. 1 개의 참된 리터럴이있는 모든 절을 모두 제거하면 과제가 반드시 여전히 독특합니까?

해결책이 고유 한 것 (다른 솔루션 문제, 공동 NP의 다른 솔루션 문제)을 보여주기 위해 해상도 증명 (기하 급수적으로 길이)을 작성하려는 경우 1과 같은 조항 만 사용하여 작성할 수 있습니까? 진정한 리터럴?

직관적으로, 나는 그렇게 생각하지만, 2sAT 상당에 대해 생각할 때도 내 관점을 방어 할 수 없다.

Answer 1

다음 CNF를 고려하십시오. $$ (a \ lor \ lnot b) \ 랜드 (\ lnot \ lor b) \ 땅 (\ lor b). $$ 그것은 독특한 만족스러운 할당, $ a= b=top $ 을 두 번 만족합니다.그러나 마지막 절을 제거한 경우 다른 만족스러운 할당, $ a= b=bot $ 을 얻습니다.