Полиномиальный временной счетчик решений экспрессии 2SAT с чистыми литералами

Question

Согласно названию, есть ли какие-либо алгоритм полиномиального времени для подсчета количества удовлетворяющих аргументов для выражения 2SAT с чистыми литералами?Еще более мелкий корпус: есть ли такой счетчик, когда литералы в выражении в выражении либо все положительные, либо все отрицательные?

Answer 1

Подсчет количества удовлетворяющих заданий в положительной формуле 2SAT, совпадает с подсчетом количества крышек вершин в соответствующем графике (после удаления синглтонных пунктов).Известно, что количество крышек вершин, как известно, $ \ mathsf {\ # p} $ - Предметы.См. Также Этот вопрос на cstheory,