纯文字2SAT表达解的多项式时间柜

Question

根据标题，是否有任何多项式时间算法来计算与纯文字的2SAT表达式的令人满意的参数的数量？甚至较浅的情况：当表达中的文字都是阳性的，或者全部负面呢？

Answer 1

计数正2SAT公式中的满足分配的数量与计数相应图中的顶点盖数（在删除单例条款后）相同。计算顶点封面的数量是 $ \ mathsf {\＃p} $ -complete。另请参阅这个问题在cstheory。