多項式（またはより現実的にはO（N ^ 2））であることが知られているブール充足可能性問題の特殊なケースについて学ぶことに興味があります。これらのケースには、満足のいくすべてのインスタンスを実際に生成するための効率的なアルゴリズムも必要です。効率的とは、すべてのインスタンスのシーケンスを生成するのにO（N #SAT）が必要であることを意味します。2番目の条件が最初の条件を暗示している可能性はありますが、私にはわかりません。
簡単な例：1SAT :)
簡単な例：2SATに句の「チェーン」があるため、変数と句を結ぶグラフは線になります。
もっとどこかにリストはありますか？ありがとう。
シェーファーによる充足可能性問題の複雑さから:
(P != NP と仮定して) SAT(S) は、次の条件の少なくとも 1 つが成り立つ場合にのみ、多項式時間で決定可能であることを示します。
(a) すべての変数が 0 の場合、S のすべての関係が満たされます。
(b) すべての変数が 1 の場合、S のすべての関係が満たされます。
(c) S のすべての関係は、各結合が最大 1 つの否定変数を持つ CNF 式によって定義可能です。
(d) S のすべての関係は、各結合が最大 1 つの非否定変数を持つ CNF 式によって定義可能です。
(e) S のすべての関係は、各結合に最大 2 つのリテラルを持つ CNF 式によって定義できます。
(f) S のすべての関係は、2 要素体 {0,1} 上の線形方程式系の解の集合です。
最初の 2 つは解決可能な O(1)、次の 3 つの O(n)、最後の O(n^3) です (私はそう思います)。したがって、必要な SAT インスタンスは、最初の 5 つのクラスのいずれかに属します。