고유 한 진실 할당이 존재하는지 여부에 관계없이 2에 만족성 문제가 발생합니다

Question

2-SAT 문제의 확장 인 문제가 있습니다. 표준 2-SAT 문제에서, 우리는 우리가 선택한 정점의 순서에 따라 달라지는 진실 할당을 찾을 수 있습니다. 표현이 만족할 수있는 하나의 진실 할당 (즉 하나의 조합)이 존재하는지 확인하고 싶습니다. 리터럴의 수는 100000 일 수 있습니다. 한 가지 방법은 가능한 모든 진실 할당을 찾은 다음 뚜렷한 경우 비교하는 것입니다. 그러나 문제는 각 비교에 대한 문제는 100000 값 (리터럴 없음)을 비교해야합니다. 효율적인 방법이 있습니까?

Answer 1

Feder (1994). 알고리즘에 대한이 기사에는 과제 수를 계산하기위한 인용이 있지만 두 가지 과제를 나열하면 더 효율적일 수 있습니다.