Contador de tempo polinômio de soluções de expressão de 2,sat com literais puros

Question

De acordo com o título, há algum algoritmo de tempo polinomial para contar o número de argumentos satisfatórios para uma expressão de 2,sat com literais puros?Um caso ainda mais raso: existe algum tal contador quando os literais na expressão são todos positivos, ou todos negativos?

Answer 1

Contando o número de tarefas satisfatórias em uma fórmula positiva de 2sat é a mesma que contando o número de capas de vértice no gráfico correspondente (depois de remover cláusulas Singleton).Contando o número de capas de vértice é conhecido por ser $ \ mathsf {\ # p} $ -complete.Veja também Esta questão em cstheory.