2-satisfiability とは

コンピュータ科学では、2-satisfiability、2-SATまたは単に2SATは、変数の対に関する制約のシステムを満たすために、それぞれが2つの可能な値を有する変数に値を割り当てる計算上の問題である。これは、2つ以上の変数に対する制約と、各変数の値に対して2つ以上の選択肢を可能にする制約満足問題の一般的なブール充足可能性問題の特殊なケースです。しかし、NP完全であるこれらのより一般的な問題とは対照的に、2充足可能性は多項式時間で解くことができる。
2適合性問題のインスタンスは、通常、結合正規形(2-CNF)またはクロム式と呼ばれる特別な種類のブール式として表現されます。あるいは、それらは、有向グラフの特殊なタイプ、グラフのインスタンスとしての変数およびその否定を頂点として表現する含意グラフ、および有向枝としての変数対に関する制約として表現することができる。これらの種類の入力は両方とも、バックトラッキングに基づく方法または含意グラフの強連結成分を用いることによって、線形時間で解くことができる。分解能は、制約のペアを組み合わせて追加の有効な制約を作成する方法でもあり、多項式時間の解を導きます。 2適合性の問題は、多項式時間で解くことができる結合論理式の2つの主要なサブクラスのうちの1つを提供する。 2つのサブクラスのうちのもう1つは、ホーン満足度です。
オブジェクトの集合がそれぞれ2つの潜在的な場所を持ち、目標は他のオブジェクトとの重なりを避ける各オブジェクトの配置を見つけることであるジオメトリおよび視覚化の問題に適用可能です。他のアプリケーションには、クラスターの直径の合計を最小化するためのデータのクラスター化、クラスルームとスポーツのスケジューリング、および断面に関する情報からの形状の回復が含まれます。
計算複雑性理論では、2充足可能性は、NL完全問題の例を提供する.NL完全問題は、対数記憶量を使用して非決定論的に解くことができ、このリソース境界で解決可能な問題の中で最も難しい問題の1つである。 2適合性インスタンスに対するすべての解の集合は、メジアングラフの構造を与えることができるが、これらの解を数えることは#P完了であり、したがって、多項式時間解を有することは期待されない。変数と制約の比が1を超えて増加するにつれて、無作為のインスタンスは解決可能なインスタンスから解けないインスタンスに急激な相転移を起こします。これは、より複雑な形の充足可能性の問題に対しては証明されていません。満足度の制約の数を最大にする真理値の割り当てを求める計算困難な2適合性のバリエーションは、固有のゲームの推測に依存する近似アルゴリズムと、真の変数の数を最小にする満足のいく割り当てを見つける別の困難なバリエーションを持ち、パラメータ化された複雑さのための重要なテストケースです。