純粋なリテラルによる2SAT表現の解の多項式時間カウンタ

Question

タイトルに従って、純粋なリテラルを持つ2SAT式の満足度引数の数を数える多項式の時間アルゴリズムはありますか？浅いケース：式のリテラルがすべて正の、またはすべての否定的なものである場合、そのようなカウンターはありますか？

Answer 1

肯定的な2SAT式の満足課題の数値の数値は、対応するグラフ内の頂点カバーの数をカウントする（シングルトン句を削除した後）。頂点カバーの数をカウントすることは、 $ \ mathsf {\＃p} $ -completeです。 cStheoryでのこの質問。