Sharp-SAT とは

計算複雑性理論では、ブール充足可能性問題に関連する関数問題である#SATまたはSharp-SATは、特定のブール式の充足する割り当ての数を数える問題です。これは、計算上の複雑さの理論に特に関心がある、計数問題のクラスのよく知られている例です。
どのNPマシンもクックの定理と同様のプロセスでブール式に符号化することができるので、ブール式の充足する割り当ての数は次のようになる。 NPマシン。 SATの数式は3-CNF形式の式として書き直すことができるため、#SATと#3SATは等価であり、#3SATも#P完了です。