On collapse of the polynomial hierarchy if NP is in non-uniform polynomial time class
複雑性理論 において 、 カープ・リプトンの定理は、 ブール充足可能性問題（SAT）が 多項式 数の論理ゲート を持つ ブール回路 で解ける 場合、
Π 2 = Σ 2 {\displaystyle \Pi _{2}=\Sigma _{2}\,} そしてそれゆえ P H = Σ 2 . {\displaystyle {\mathsf {PH}}=\Sigma _{2}.\,} つまり、非決定性多項式時間問題のクラス NPが 非一様多項式時間 計算量クラス P/poly に含まれると仮定すると 、この仮定は 多項式階層 の第 2 レベルでの崩壊を意味します。このような崩壊は起こりにくいと考えられているため、この定理は複雑性理論家によって一般に、SAT またはその他の NP 完全 問題に対する多項式サイズの回路が存在しない証拠と見なされています。このような回路が存在しないという証明は、 P ≠ NP を意味します。 P/poly にはランダム化多項式時間で解けるすべての問題が含まれているため ( アドルマンの定理 )、この定理はランダム化を使用しても NP 完全問題に対する多項式時間アルゴリズムは得られないことの証拠でもあります。
カープ・リプトンの定理は、 1980 年に最初に証明した リチャード・M・カープ と リチャード・J・リプトン にちなんで名付けられました。(彼らの最初の証明では PH が に縮小されましたが、 マイケル・シプサーが それを に改良しました 。) Σ 3 {\displaystyle \Sigma _{3}} Σ 2 {\displaystyle \Sigma _{2}}
定理の変形では、同じ仮定の下で、 MA = AM となり、 PHは S に収束する。 P2 複雑度クラス 。PSPACE や他の複雑度クラスが多項式サイズの回路を持つと仮定すれば、より強い結論が得られる可能性がある。P/polyを参照のこと 。NP が BPP（P/polyのサブセット）のサブセットであると仮定すると、多項式階層は BPP に縮小される。 [1] coNPが NP/poly のサブセットであると仮定すると 、多項式階層は第3レベルに縮小される。
直感 SATのための多項式サイズの回路が存在するだけでなく、それらが多項式時間アルゴリズムで構築できると仮定する。この仮定は、SAT自体が、回路を構築し、それを適用する多項式時間アルゴリズムによって解けることを意味する。つまり、SATのために効率的に構築可能な回路は、より強い崩壊、すなわちP = NPをもたらす。
カープ・リプトン定理の仮定、すなわちこれらの回路が存在するという仮定は、より弱い。しかし、計算量クラスのアルゴリズムが SATの正しい回路を 推測する ことは依然として可能である。計算量クラスは 、次のような形式の問題を記述する。 Σ 2 {\displaystyle \Sigma _{2}} Σ 2 {\displaystyle \Sigma _{2}}
∃ x ∀ y ψ ( x , y ) {\displaystyle \exists x\forall y\;\psi (x,y)} ここで 、 は任意の多項式時間計算可能な述語です。この述語の最初の量指定子の存在べき乗は、SATの正しい回路を推測するために使用でき、2番目の量指定子の普遍べき乗は、その回路が正しいことを検証するために使用できます。この回路が推測され検証されると、クラスのアルゴリズムは それを他の問題を解くためのサブルーチンとして使用できます。 ψ {\displaystyle \psi } Σ 2 {\displaystyle \Sigma _{2}}
自己還元性 カープ・リプトンの証明をより詳細に理解するために、回路 c が 与えられたサイズの SAT インスタンスを解くための正しい回路であるかどうかをテストする問題を考察し、この回路テスト問題が に属することを示します 。つまり、多項式時間で計算可能な述語 Vが存在し、 c が 正しい回路である ための必要 条件 は、すべての多項式的に制限された z に対して、 V ( c , z ) が真であることです。 Π 1 {\displaystyle \Pi _{1}}
回路 c は、次の 2 つの特性を満たす場合、SAT にとって正しい回路です。
s がSATのインスタンスであり、 x が そのインスタンスの解である すべてのペア ( s , x )について、 c ( s ) は真でなければならない。 c ( s )が真となる SATの すべてのインスタンス sについて、 sは 解ける必要があります。 これら2つの特性のうち、最初の特性は既にクラス の問題として現れています。2つ目の特性を検証するために、SATの 自己還元性 特性を利用します 。 Π 1 {\displaystyle \Pi _{1}}
自己還元性とは、SATインスタンスが解けるかどうかを素早くテストできれば、そのインスタンスの明示的な解もほぼ同程度に素早く見つけられるという現象を指します。インスタンス sの解を見つけるには、 s に入力される ブール変数 x の1つを選択し、2つの小さなインスタンス s 0 と s 1 を作成します。ここで、 s i は x を 定数 i に置き換えて得られる式を表します 。これらの2つの小さなインスタンスが構築されたら、それぞれに解けるかどうかのテストを適用します。2つのテストのいずれかで、小さなインスタンスが満足可能であると判定された場合、完全な解が導出されるまでそのインスタンスの解決を続けます。
自己還元性を使用して SAT の正しい回路の 2 番目のプロパティを確認するには、次のように書き直します。
c ( s )が真となるSATの すべてのインスタンス s について、上記の自己簡約手順により s の有効な解が見つかります。 したがって、 c が SAT を解決するための有効な回路
で あるかどうか をテストできます。 Π 1 {\displaystyle \Pi _{1}}
詳細については、 「ランダム自己還元可能性」 を参照してください。
カープ・リプトン定理の証明 カープ・リプトンの定理は、多項式的に有界な量指定子を持つブール式に関する結果として言い換えることができる。 このタイプの式は、次のような構文で記述される。 Π 2 {\displaystyle \Pi _{2}}
ϕ = ∀ x ∃ y ψ ( x , y ) {\displaystyle \phi =\forall x\exists y\;\psi (x,y)} ここで 、は多項式時間で計算可能な述語である。カープ・リプトンの定理によれば、この種の式は、量指定子が逆の順序で現れる等価な式に多項式時間で変換できる。このような式は に属する 。部分式 ψ {\displaystyle \psi } Σ 2 {\displaystyle \Sigma _{2}}
s ( x ) = ∃ y ψ ( x , y ) {\displaystyle s(x)=\exists y\;\psi (x,y)} はSATのインスタンスである。つまり、 cが SATの有効な回路である場合、この部分式は非量化式 c ( s ( x ) )と等価である。したがって、の完全な式は（有効な回路 cが 存在するという仮定の下で ）次の式と
等価である。 ϕ {\displaystyle \phi }
∃ c ∀ ( x , z ) V ( c , z ) ∧ c ( s ( x ) ) {\displaystyle \exists c\forall (x,z)\;V(c,z)\wedge c(s(x))\,} ここで、 V は、上述のように自己還元可能性を用いて cが 本当に有効な回路であることを検証するために使用される式である。この等価式は、期待どおりに量指定子の順序が逆になっている。したがって、Karp-Lipton仮定により、この種の式において存在量指定子と全称量指定子の順序を入れ替えることができ、次のようになる 。この入れ子構造を繰り返すことで、より深いネストを持つ式を、単一の存在量指定子とそれに続く単一の全称量指定子を持つ形に簡略化することができ、次のようになる。 Σ 2 = Π 2 . {\displaystyle \Sigma _{2}=\Pi _{2}.} P H = Σ 2 . {\displaystyle PH=\Sigma _{2}.}
もう一つの証明とS P2 と仮定する。したがって、長さ n の入力に対して充足可能性を解く 回路の族が存在する。自己還元可能性を用いると、 真のインスタンスに対して充足割り当てを出力する 回路の族が存在する。 N P ⊆ P / p o l y {\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}} C n {\displaystyle C_{n}} D n {\displaystyle D_{n}}
L が 集合
である とする Π 2 {\displaystyle \Pi _{2}}
L = { z : ∀ x . ∃ y . ϕ ( x , y , z ) } {\displaystyle L=\{z:\forall x.\exists y.\phi (x,y,z)\}\,} はSATの例とみなすことができる ので（ クック・レビン定理 により）、に依存する 回路が存在し、 Lを 定義する式は次式と 等価である。 ∃ y . ϕ ( x , y , z ) {\displaystyle \exists y.\phi (x,y,z)} D n {\displaystyle D_{n}} n = | z | {\displaystyle n=|z|}
∀ x . ϕ ( x , D n ( x , z ) , z ) {\displaystyle \forall x.\phi (x,D_{n}(x,z),z)} 1
さらに、存在量化 によって回路を推測することができます 。
∃ D . ∀ x . ϕ ( x , D ( x , z ) , z ) {\displaystyle \exists D.\forall x.\phi (x,D(x,z),z)} 2
明らかに( 1 )は( 2 )を意味する。(1)が偽ならば、となる 。この場合、回路 Dは 真となる割り当てを出力することはできない 。 ¬ ∃ y . ϕ ( x , y , z ) {\displaystyle \neg \exists y.\phi (x,y,z)} ϕ ( x , D ( x , z ) , z ) {\displaystyle \phi (x,D(x,z),z)\;}
証明により、 集合は に含まれることが示されました 。 Π 2 {\displaystyle \Pi _{2}} L {\displaystyle L} Σ 2 {\displaystyle \Sigma _{2}}
さらに、 式が真であれば、回路 Dは任意の x に対して作用する 。 式が偽であれば、式(1)を偽とする xは 任意の回路に対して作用する。この性質は、より強い崩壊、すなわち Sへの崩壊を意味する。 Π 2 {\displaystyle \Pi _{2}} Π 2 {\displaystyle \Pi _{2}} P2 複雑性クラス（すなわち ）。これはセングプタによって観察された。 [2] Π 2 ⊆ S 2 P ⊆ Σ 2 {\displaystyle \Pi _{2}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}}
午前 = 午前 上記の証明を 修正すると [3]、
N P ⊆ P / p o l y ⟹ A M = M A {\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}\implies {\mathsf {AM}}={\mathsf {MA}}} （ アーサー・マーリン・プロトコルを 参照）。
Lが AM にある と仮定します 。つまり、
z ∈ L ⟹ Pr x [ ∃ y . ϕ ( x , y , z ) ] ≥ 2 3 {\displaystyle z\in L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\geq {\tfrac {2}{3}}} z ∉ L ⟹ Pr x [ ∃ y . ϕ ( x , y , z ) ] ≤ 1 3 {\displaystyle z\notin L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\leq {\tfrac {1}{3}}} そして、 満足する割り当てが存在する場合にそれを出力する 回路を使用して、前と同じように書き直します。 ∃ y . ϕ ( x , y , z ) {\displaystyle \exists y.\phi (x,y,z)} D n {\displaystyle D_{n}}
z ∈ L ⟹ Pr x [ ϕ ( x , D n ( x , z ) , z ) ] ≥ 2 3 {\displaystyle z\in L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\geq {\tfrac {2}{3}}} z ∉ L ⟹ Pr x [ ϕ ( x , D n ( x , z ) , z ) ] ≤ 1 3 {\displaystyle z\notin L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\leq {\tfrac {1}{3}}} 推測できる のは: D n {\displaystyle D_{n}}
z ∈ L ⟹ ∃ D . Pr x [ ϕ ( x , D ( x , z ) , z ) ] ≥ 2 3 {\displaystyle z\in L\implies \exists D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\geq {\tfrac {2}{3}}} z ∉ L ⟹ ∀ D . Pr x [ ϕ ( x , D ( x , z ) , z ) ] ≤ 1 3 {\displaystyle z\notin L\implies \forall D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\leq {\tfrac {1}{3}}} これは、 より小さいクラス MA に属することを証明します。 L {\displaystyle L}
回路下界への応用 – カンナンの定理 カンナン の定理 [4] によれば、任意の固定された kに対して、 SIZE (n k )に含まれない 言語が に存在する （これは現在未解決の とは異なる定理であり、任意の kに対して SIZE (n k )に 含まれない単一の言語が存在すると述べている ）。これは単純な 回路の下限で ある。 L {\displaystyle L} Σ 2 {\displaystyle \Sigma _{2}} Σ 2 ⊈ P / p o l y {\displaystyle \Sigma _{2}\not \subseteq {\mathsf {P/poly}}}
証明の概要:
言語が存在する （証明には 対角化 技法を用いる）。以下の2つのケースを考えてみよう。 L ∈ Σ 4 − S I Z E ( n k ) {\displaystyle L\in \Sigma _{4}-{\mathsf {SIZE}}(n^{k})}
すると 、 定理が証明されます。 S A T ∉ P / p o l y {\displaystyle {\mathsf {SAT}}\notin {\mathsf {P/poly}}} S A T ∉ S I Z E ( n k ) {\displaystyle {\mathsf {SAT}}\notin {\mathsf {SIZE}}(n^{k})} ならば 、Karp–Lipton定理により、 となり、 したがって となります 。 S A T ∈ P / p o l y {\displaystyle {\mathsf {SAT}}\in {\mathsf {P/poly}}} Σ 4 = Σ 2 {\displaystyle \Sigma _{4}=\Sigma _{2}} L ∈ Σ 2 − S I Z E ( n k ) {\displaystyle L\in \Sigma _{2}-{\mathsf {SIZE}}(n^{k})} Karp-Lipton 定理のより強力なバージョンは Kannan の定理を強化し、任意の k に対して言語 が存在するようにします 。 L ∈ S 2 P − S I Z E ( n k ) {\displaystyle L\in {\mathsf {S}}_{2}^{P}-{\mathsf {SIZE}}(n^{k})}
PP は に含まれない ことも知られており 、これはヴィノドチャンドランによって証明された。 [5] 証明: [6] S I Z E ( n k ) {\displaystyle {\mathsf {SIZE}}(n^{k})}
もし そうなら 。 P P ⊈ P / p o l y {\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {P/poly}}} P P ⊈ S I Z E ( n k ) {\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {SIZE}}(n^{k})} そうでなけれ ば、 P # P ⊆ P / p o l y {\displaystyle {\mathsf {P^{\#P}}}\subseteq {\mathsf {P/poly}}} P # P ⊇ P P ⊇ M A {\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PP}}\supseteq {\mathsf {MA}}} （ MA の所有物 ） P # P ⊇ P H ⊇ Σ 2 ⊇ M A {\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PH}}\supseteq \Sigma _{2}\supseteq {\mathsf {MA}}} （ 戸田の定理 とMAの性質により） P # P = M A {\displaystyle {\mathsf {P^{\#P}}}={\mathsf {MA}}} （永続的な対話型プロトコルを使用するという仮定に従う。P /polyを 参照） 包含関係は等式であり、 カンナンの定理によって得られます。 P P = Σ 2 ⊈ S I Z E ( n k ) {\displaystyle {\mathsf {PP}}=\Sigma _{2}\not \subseteq {\mathsf {SIZE}}(n^{k})}
参考文献 ^ S. Zachos , 確率的量化子とゲーム, 1988 ^ ジン・イーカイ。 [1]、セクション 6 S 2 P ⊆ Z P P N P {\displaystyle S_{2}^{P}\subseteq {\mathsf {ZPP}}^{\mathsf {NP}}} ^ V. Arvind、J. Köbler、 U. Schöning 、R. Schuler、「NP に多項式サイズの回路がある場合、MA = AM」 ^ Kannan, R. (1982). 「回路サイズの下限値とスパース集合への非還元性」. 情報制御 . 55 ( 1– 3): 40– 56. doi :10.1016/S0019-9958(82)90382-5. hdl : 1721.1/149016 . ^ NV Vinodchandran, PPの回路複雑性に関する注記 ^ S. アーロンソン 、「オラクルには微妙なニュアンスがあるが、悪意はない」 カープ, RM ; RJ リプトン (1982)、「アドバイスを受けるチューリング マシン」、 L'Enseignement Mathématique 、 28 : 191–209 、 doi :10.5169/seals-52237 。 
![{\displaystyle z\in L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\geq {\tfrac {2}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/093bd2440f576a4a1d2c930469cfb9614b94d1b7)
![{\displaystyle z\notin L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\leq {\tfrac {1}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d79a1999c83a1787553fce47777e28ecb33f7da)
![{\displaystyle z\in L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\geq {\tfrac {2}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23b2ba2151117f23c0eb15bb045878548b12bd26)
![{\displaystyle z\notin L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\leq {\tfrac {1}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b448e5eab161fd5376a8f746e43b0854800ab5e)
![{\displaystyle z\in L\implies \exists D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\geq {\tfrac {2}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6b7ec4305936400c7fbabd6a716ddc36627659a)
![{\displaystyle z\notin L\implies \forall D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\leq {\tfrac {1}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c49d8e45577b40ec55200616470795be76f3cda)
