순수 리터럴과 2SAT 발현의 해결책의 다항식 시간 카운터

Question

타이틀에 따라 순수 리터럴이있는 2SAT 발현을위한 만족스러운 인수의 수를 계산하는 다항식 시간 알고리즘이 있습니까?심지어 얕게 케이스 : 표현의 리터럴이 모두 양성 또는 모든 음수이거나 모든 카운터가 있습니까?

Answer 1

양의 2SAT 수식에서 만족하는 할당의 수를 계수하는 것은 해당 그래프의 정점 덮개 수를 카운트하는 것과 동일합니다 (싱글 톤 절을 제거한 후).정점 덮개 수를 계산하는 것은 $ \ mathsf {\ # p} $ -complete로 알려져 있습니다.이 질문 in cstheory..