2-Satisfiability 문제 - 고유 한 진리 할당이 존재하는지 여부

Question

2-SAT 문제의 확장 문제입니다. 표준 2-SAT 문제에서, 우리는 우리가 선택한 정점의 순서에 의존하는 진리 할당을 찾을 수 있습니다. 나는 그 표현이 만족할 수있는 오직 하나의 진리 과제 (즉, 오직 하나의 조합)가 존재 하는지를 확인하기를 원한다. 리터럴 수는 100000 일 수 있습니다. 한 가지 방법은 모든 가능한 진리 할당을 찾아서 구별되는 경우 비교하는 것입니다. 그러나 문제는 각각의 비교를 위해, 나는 100000 값 (리터럴 없음)을 비교해야 할 것입니다. 어떤 효율적인 방법이 있습니까?

Answer 1

Feder (1994) describes an algorithm for efficiently listing all solutions to a given 2-satisfiability instance. 이 기사에는 할당 수를 계산하는 알고리즘에 대한 인용문이 있지만보다 효율적일 수있는 두 개의 할당 만 나열하면됩니다.