すべてが等しくない 3 満足可能性

計算複雑性において、すべて等しいわけではない3-充足可能性（NAE3SAT）は、ブール充足可能性問題のNP完全変種であり、NP完全性の証明でよく使用されます。^[1]

3-充足可能性と同様に、問題のインスタンスはブール変数のコレクションと節のコレクションで構成され、各節は3つの変数または変数の否定を組み合わせています。ただし、各節に少なくとも1つの真のブール値が必要であることを要求する3-充足可能性とは異なり、NAE3SATでは、各節の3つの値がすべて互いに等しくないことが要求されます（つまり、少なくとも1つは真であり、少なくとも1つは偽です）。^[2]

NAE3​​SATのNP完全性は、3-充足可能性（3SAT）からの縮約によって証明できます。 ^[2]まず、非対称3SATは、すべての節に共通のダミーリテラルを追加することで対称NAE4SATに縮約され、次に、一般的な-充足可能性を3SATに縮約する場合と同様に、節を分割することでNAE4SATはNAE3SATに縮約されます。 ${\displaystyle s}$${\displaystyle k}$

より詳細には、3SAT インスタンス( は任意のリテラル) は、が新しい変数であるNAE4SAT インスタンスに簡約されます。を設定することにより、に対する満足な割り当ては、に対する満足な割り当てになります。逆に、 に対する満足な割り当ては、各節に少なくとも 1 つの他のリテラルが true でなければならないため、 に対する満足な割り当てになります。最後に、 と の対称性により、 に対する満足な割り当てを反転して、に対する満足な割り当てを生成できます。 ${\displaystyle \Phi =\bigwedge _{i=1}^{m}(l_{i,1}\vee l_{i,2}\vee l_{i,3})}$${\displaystyle l_{i,j}}$${\displaystyle \Psi =\bigwedge _{i=1}^{m}(l_{i,1},l_{i,2},l_{i,3},s)}$${\displaystyle s}$${\displaystyle \Phi}$${\displaystyle \Psi}$${\displaystyle s=0}$${\displaystyle s=0}$${\displaystyle \Psi}$${\displaystyle \Phi}$${\displaystyle s=1}$${\displaystyle \Psi}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle s=0}$

NAE3​​SATは、シェーファーの二分法定理により、すべての節が単調（つまり、変数が否定されない）である場合にNP完全のままである。^{[3]単調なNAE3SATは、}集合分割問題の一例、またはグラフ二部性テストの3-ユニフォームハイパーグラフへの一般化として も解釈できる。これは、ハイパーグラフの頂点を2色で着色して、ハイパーエッジが単色にならないかどうかを問うものである。より強い言い方をすると、2色着色が存在する場合でも、任意の定数数の色で3-ユニフォームハイパーグラフの着色を見つけることはNP困難である。^[4]

3SATとは異なり、変数と節の構造を表すグラフが平面グラフであるNAE3SATのいくつかの変種は、多項式時間で解くことができます。特に、変数ごとに1つの頂点、節ごとに1つの頂点、変数と節の発生ごとに1つの辺、およびすべての変数の頂点を接続する辺のサイクルを持つ平面グラフが存在する場合にこれが当てはまります。^[5]