k-CNF充足可能性問題

k-CNF SAT

各節のリテラルが最大k個の連言標準形論理式が充足可能かを問う決定問題で、k≥3ならNP完全である。

記事1本最終言及

k-CNF SAT(k-SAT)は、各節(クローズ)に最大k個のリテラルを含む連言標準形(CNF)のブール論理式について、すべての節を同時に真にする変数の割り当てが存在するかを問う決定問題である。充足可能性問題(SAT)の特殊な場合で、2-SATは多項式時間で解けるが、3-SATをはじめk≥3の場合はNP完全である。

SATは1971年にスティーヴン・クックがNP完全であることを証明した最初の問題であり、3-SATは他の問題のNP困難性を示す帰着の出発点として広く使われる。変数がn個のとき全割り当てを試すと2^n時間がかかり、2^{cn}(c<1)時間で動作するアルゴリズムが知られている。指数時間仮説(ETH)は、この問題を準指数時間で解けないとする予想である。実務ではSATソルバーがハードウェア・ソフトウェア検証や計画問題などに用いられる。

この説明は、AIPOSTの記事と広く知られた事実をもとにまとめたものです。誤りがあれば訂正依頼でお知らせください。

この項目を扱った記事

  • OpenAIのAIが指数時間仮説を反証、P=NPではないが理論の土台が揺らぐAIニュース ·

    約30年前にラッセル・インパリアッツォ氏、ラマモハン・パトゥリ氏、フランシス・ゼイン氏が提唱したこの仮説は、この問題のk-CNF版を解くには、変数の数に対して厳密に指数的に増大する時間が必要だと主張していました。

    記事を読む

説明の誤りや、見つからない項目はありますか?

事典の説明は、AIPOSTの記事と広く知られた事実をもとにまとめています。誤りは訂正依頼でお知らせいただければ、確認して修正します。新しい記事に登場した名前は、記事の公開後に事典に加わります。