シェーファーの二分法定理

計算機科学の一分野である計算複雑性理論において、トーマス・ジェローム・シェーファーによって証明されたシェーファーの二分法定理は、ブール領域上の関係の有限集合S が、命題変数の一部を制約するためにSの関係を使用した場合に、多項式時間問題またはNP 完全問題を生成するための必要十分条件を述べています。^[1] この定理が二分法定理と呼ばれるのは、 Sによって定義される問題の複雑性がP 内にあるか NP 完全であるからであり、ラドナーの定理によって存在が知られている中間の複雑性のクラスの 1 つ( P ≠ NPと仮定)とは対照的です。

シェーファーの二分法定理の特殊なケースとしては、SAT (ブール充足問題)の NP 完全性と、その 2 つの一般的な変種である1-in-3 SATとnot-all-equal 3SAT (NAE-3SAT と表記されることが多い) があります。実際、SAT のこれら 2 つの変種について、シェーファーの二分法定理は、単調バージョン (変数の否定が許可されない) も NP 完全であることを示しています。

シェーファーは、Sの一般化充足可能性問題(SAT( S ) と表記)と呼ぶ決定問題を定義します。ここで、はバイナリ領域 上の関係の有限集合です。問題のインスタンスはS式、つまり の形式の制約の連言です。ここで、およびは命題変数です。問題は、指定された式が充足可能かどうか、つまり、 Sの関係によって与えられたすべての制約を満たすように変数に値を割り当てることができるかどうかを判断することです。 ${\displaystyle S=\{R_{1},\ldots ,R_{m}\}}$${\displaystyle \{0,1\}}$${\displaystyle R_{j}(x_{i_{1}},\dots ,x_{i_{n}})}$${\displaystyle R_{j}\in S}$${\displaystyle x_{i_{j}}}$

シェーファーは、SAT( S )がPに含まれるブール関係の集合の6つのクラスを特定し、他のすべての関係集合がNP完全問題を生成することを証明しています。ブール領域上の関係の有限集合Sは、次の条件のいずれかが満たされる場合、多項式時間で計算可能な充足可能性問題を定義します。

1. 常に偽ではないすべての関係は、そのすべての引数が真であるときに真になります。
2. 常に偽ではないすべての関係は、そのすべての引数が偽であるときに真になります。
3. すべての関係は二項節の結合と同等である。
4. すべての関係はホーン節の結合と同等である。
5. すべての関係は、二重ホーン節の結合と同等である。
6. すべての関係はアフィン式の連言と同等である。^[2]

それ以外の場合、問題SAT( S )はNP完全です。

シェーファーの定理の現代的で簡潔な表現は、Hubie Chen による解説論文で示されています。^{[3] [4]}現代的な用語では、問題 SAT( S ) はブール領域上の制約充足問題と見なされます。この分野では、関係の集合を Γ で表し、 Γ によって定義された決定問題を CSP(Γ) と表記するのが標準です。

この現代的な理解では、代数、特に普遍代数が用いられます。シェーファーの二分法定理にとって、普遍代数における最も重要な概念は多態性の概念です。ある操作が関係の多態性とは、 Rから任意のm個の組を選択して、これらのm個の組からf を座標的に適用して得られる組、すなわち がRに含まれる場合です。つまり、 Rがfに関して閉じている場合、つまり、 R 内の任意の組にf を適用すると、R内に別の組が生成された場合、操作fはRの多態性です。関係の集合 Γ は、 Γ 内のすべての関係が f を多態性として持つ場合、多態性 f を持つと言われています。この定義により、シェーファーの二分法定理の代数的定式化が可能になります。 ${\displaystyle f:D^{m}\to D}$${\displaystyle R\subseteq D^{k}}$${\displaystyle (t_{11},\dotsc ,t_{1k}),\dotsc ,(t_{m1},\dotsc ,t_{mk})}$${\displaystyle (f(t_{11},\dotsc ,t_{m1}),\dotsc ,f(t_{1k},\dotsc ,t_{mk}))}$

Γ をブール領域上の有限制約言語とします。Γ が多態性として次の 6 つの演算のいずれかを持つ場合、問題 CSP(Γ) は多項式時間で決定可能です。

1. 定数単項演算 1;
2. 定数単項演算 0;
3. バイナリAND演算∧;
4. バイナリOR演算∨;
5. 三項多数決 ${\displaystyle \operatorname {多数決} (x,y,z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z);}$
6. 三元少数派演算${\displaystyle \operatorname {少数派} (x,y,z)=x\oplus y\oplus z.}$

それ以外の場合、問題CSP(Γ)はNP完全です。

この定式化では、いずれかの扱いやすさの条件が満たされているかどうかを簡単に確認できます。

関係の集合 Γ が与えられた場合、その多態性と CSP(Γ) の計算複雑性の間には驚くほど密接な関係があります。

関係Rは、関係の集合 Γ から、R ( v ₁ , ... , v _k ) ─ ∃ x ₁ ... x _mであるとき、原始正値定義可能、または略してpp 定義可能 と呼ばれる。Cは、 Γからの制約と変数 { v ₁ ,..., v _k , x ₁ ,..., x _m } に関する方程式との何らかの連言 Cに対して成立する。たとえば、 Γ が、x、y、zがすべて等しくなく、R ( x、y、 z ) がx ∨ y ∨ zである場合に成立する三項関係nae ( x 、 y 、 z ) から構成される場合、 R は R ( x、y、z ) ─ ∃ aによってpp定義できる。nae ( 0 , x 、a ) ∧ nae ( y、z、¬ a )。この簡約はNAE-3SATがNP完全であることを証明するために使われてきた。Γからpp定義可能なすべての関係の集合は、≪Γ≫と表記される。ある有限制約集合ΓとΓ'に対してΓ'⊆≪Γ≫であれば、CSP(Γ')はCSP(Γ)に簡約される。 ^[5]

関係の集合 Γ が与えられたとき、Pol (Γ) は Γ の多態性の集合を表す。逆に、O が演算の集合である場合、Inv ( O ) はOのすべての演算を多態性として持つ関係の集合を表す。Pol とInv は一緒に反トーンガロア接続を形成する。有限領域上の関係の任意の有限集合 Γ に対して、«Γ» = Inv ( Pol (Γ)) が成り立つ。つまり、Γ から pp 定義可能な関係の集合は、Γ の多態性から導出できる。^[6]さらに、 2 つの有限関係集合 Γ と Γ' に対してPol (Γ) ⊆ Pol (Γ') である場合、Γ' ⊆ ≪Γ≫ となり、CSP(Γ') は CSP(Γ) に簡約される。結果として、同じ多態性を持つ 2 つの関係集合は、同じ計算量につながる。^[7]

この解析は後に微調整され、CSP(Γ)はco-NLOGTIME、L完全、NL完全、⊕L完全、P完全、NP完全のいずれかで解けるようになり、Γが与えられれば、これらのケースのどれが成り立つかを多項式時間で決定できるようになった。^[8]

シェーファーの二分法定理はブール論理の代わりにグラフの命題論理を使用するように一般化されている。 ^[9]

問題が解の数を数えることである場合、それは#CSP(Γ)で表され、CreignouとHermannによるバイナリ領域に対しても同様の結果があります。^[10] 具体的には、ブール領域上の関係の有限集合Sは、 S内のすべての関係がアフィン式の連言に等しい場合、多項式時間で計算可能な充足可能性問題を定義します。 ^[2]

より大きな領域では、多項式時間で満足可能であるための必要条件が Bulatov と Dalmau によって与えられました。^[11] Γ をブール領域上の有限制約言語とします。問題 #CSP(Γ) が多項式時間で計算可能であれば、 Γ には多態性としてMal'tsev演算があります。そうでない場合、問題 #CSP(Γ) は#P 完全です。 Mal'tsev 演算mは、次を満たす 3 項演算です。 Mal'tsev 演算の例は、上記の Schaefer の二分法定理の現代的な代数的定式化で与えられた少数演算です。したがって、 Γ に多態性として少数演算がある場合、 CSP(Γ) を多項式時間で決定できるだけでなく、 #CSP(Γ) を多項式時間で計算することもできます。ブール変数に対するマルツェフ演算は全部で 4 つあり、およびの値によって決まります。あまり対称でない演算の例は によって与えられます。グループなどの他の領域では、マルツェフ演算の例にはや が含まれます 。より大きな領域では、サイズが 3 の領域であっても、Γ のマルツェフ多型の存在は、#CSP(Γ) の扱いやすさの不十分な条件です。ただし、Γ のマルツェフ多型が存在しないことは、#CSP(Γ) の #P 困難性を意味します。 ${\displaystyle m(x,y,y)=m(y,y,x)=x.}$${\displaystyle m(T,F,T)}$${\displaystyle m(F,T,F)}$${\displaystyle m(x,y,z)=(x\wedge z)\vee (\neg y\wedge (x\vee z))}$${\displaystyle x-y+z}$${\displaystyle xy^{-1}z.}$

• 最大/最小CSP/Ones分類定理、最適化問題に対する同様の制約セット