カープ・リプトンの定理

複雑性理論において、カープ・リプトンの定理は、ブール充足可能性問題（SAT）が多項式数の論理ゲートを持つブール回路で解ける場合、

${\displaystyle \Pi _{2}=\Sigma _{2}\,}$そのため${\displaystyle {\mathsf {PH}}=\Sigma _{2}.\,}$

つまり、非決定性多項式時間問題のクラスであるNPが、非一様多項式時間複雑性クラスP/polyに含まれると仮定すると、この仮定は多項式階層の第 2 レベルでの崩壊を意味します。このような崩壊は起こりそうにないと考えられているため、この定理は一般的に、複雑性理論家によって、SAT やその他のNP 完全問題に対する多項式サイズの回路が存在しない証拠とみなされています。このような回路が存在しないという証明は、P ≠ NPを意味します。P/poly はランダム化多項式時間で解けるすべての問題を含むため (アドレマンの定理)、この定理は、ランダム化を使用しても NP 完全問題に対する多項式時間アルゴリズムが得られないことの証拠でもあります。

カープ・リプトンの定理は、 1980年に初めてそれを証明したリチャード・M・カープとリチャード・J・リプトンにちなんで名付けられました。（彼らの最初の証明ではPHを縮約して$\displaystyle \Sigma _{3}}$しかし、マイケル・シプサーはそれを改良して$\displaystyle \Sigma _{2}}$）

この定理の変形では、同じ仮定の下で、MA = AMであり、PH はS ^P ₂複雑性クラスに縮退すると述べている。PSPACE または他のいくつかの複雑性クラスが多項式サイズの回路を持つと仮定すると、より強力な結論が得られる可能性がある。P /polyを参照。NP が BPP (P/poly の部分集合) の部分集合であると仮定すると、多項式階層はBPPに縮退する。^{[ 1 ]} coNP がNP/polyの部分集合であると仮定すると、多項式階層は第 3 レベルに縮退する。

SAT問題に対して多項式サイズの回路が存在するだけでなく、それらが多項式時間アルゴリズムで構築できると仮定します。すると、この仮定は、回路を構築して適用する多項式時間アルゴリズムによってSAT問題自体を解くことができることを意味します。つまり、SAT問題に対して効率的に構築可能な回路が存在することで、より強力な崩壊、P = NPが実現されることになります。

カープ・リプトンの定理の前提である、これらの回路が存在するという仮定は弱い。しかし、複雑性クラスのアルゴリズムでは、依然として可能である。$\displaystyle \Sigma _{2}}$SAT の正しい回路を推測する。複雑性クラス$\displaystyle \Sigma _{2}}$形式の問題を説明する

${\displaystyle \exists x\forall y\;\psi (x,y)}$

どこ${\displaystyle \psi }$は任意の多項式時間で計算可能な述語です。この述語の最初の量化子の存在力は、SAT の正しい回路を推測するために使用でき、2 番目の量化子の全称力は、回路が正しいことを検証するために使用できます。この回路が推測され検証されると、クラスのアルゴリズムが$\displaystyle \Sigma _{2}}$他の問題を解決するためのサブルーチンとして使用できます。

Karp–Lipton 証明をより詳細に理解するために、与えられたサイズの SAT インスタンスを解くための正しい回路cであるかどうかをテストする問題を考察し、この回路テスト問題が次のものに属することを示します。$\displaystyle \Pi _{1}}$つまり、多項式時間で計算可能な述語Vが存在し、 c が正しい回路であるのは、すべての多項式で制限されたzに対してV ( c , z ) が真である場合に限る。

回路cがSATにとって正しい回路であるのは、以下の2つの性質を満たす場合である。

• sがSATのインスタンスであり、xがそのインスタンスの解であるすべてのペア( s , x )について、 c ( s )は真でなければならない。
• c ( s )が真となるSATのすべてのインスタンスsについて、 sは解ける必要がある。

これら2つの性質のうち最初のものは、すでに授業で問題として出題されている。$\displaystyle \Pi _{1}}$2番目の性質を検証するために、SATの自己還元性という性質を利用します。

自己還元性とは、SAT インスタンスが解けるかどうかを素早くテストできれば、そのインスタンスの明示的な解をほぼ同じ速さで見つけることができるという現象を指します。インスタンスsの解を見つけるには、 sに入力されるブール変数xのいずれかを選択し、定数iでx を置き換えて形成される式をs _iとすると、2 つの小さなインスタンスs ₀とs ₁を作成します。これらの 2 つの小さなインスタンスが構築されたら、それぞれに解けるかどうかのテストを適用します。これらの 2 つのテストのいずれかが、小さなインスタンスが充足可能であると返した場合、完全な解が得られるまでそのインスタンスの解決を続けます。

SATの正しい回路の2番目の特性を自己還元性を用いて確認するために、それを次のように書き換えます。

• c ( s )が真であるSATのすべてのインスタンスsに対して、上記の自己還元手順はsの有効な解を見つけます。

したがって、テストできます$\displaystyle \Pi _{1}}$cがSATを解くための有効な回路であるかどうか。

詳細については、「ランダム自己還元性」を参照してください。

カープ・リプトンの定理は、多項式で制限された量化子を持つブール式に関する結果として言い換えることができる。$\displaystyle \Pi _{2}}$構文は、このタイプの式で記述されます。

${\displaystyle \phi =\forall x\exists y\;\psi (x,y)}$

どこ${\displaystyle \psi }$は多項式時間で計算可能な述語です。カープ・リプトンの定理によれば、このタイプの式は、量化子が逆の順序で現れる同値な式に多項式時間で変換できます。このような式は に属します。$\displaystyle \Sigma _{2}}$. サブ式に注意してください

${\displaystyle s(x)=\exists y\;\psi (x,y)}$

は SAT のインスタンスです。つまり、c がSAT の有効な回路である場合、この部分式は非量化式c ( s ( x )) と同等です。したがって、完全な式は${\displaystyle \phi }$（有効な回路cが存在するという仮定の下で）は、次の式と同等である。

${\displaystyle \exists c\forall (x,z)\;V(c,z)\wedge c(s(x))\,}$

ここで、Vは、上記のように自己還元性を用いてc が実際に有効な回路であることを検証するために使用される式です。この等価な式は、望ましいように、量化子の順序が逆になっています。したがって、Karp–Lipton 仮定により、この種の式における存在量化子と全称量化子の順序を入れ替えることができ、次のことが示されます。${\displaystyle \Sigma _{2}=\Pi _{2}.}$転置を繰り返すことで、より深いネストを持つ式を、単一の存在量化子の後に単一の全称量化子が続く形式に単純化することができ、次のことが示される。${\displaystyle PH=\Sigma _{2}.}$

仮定する${\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}}$したがって、回路のファミリーが存在する${\displaystyle C_{n}}$これは長さnの入力に対する充足可能性問題を解決する。自己還元性を用いると、回路の族が存在する。${\displaystyle D_{n}}$これは、真のインスタンスに対して満足のいく割り当てを出力する。

Lは​$\displaystyle \Pi _{2}}$セット

${\displaystyle L=\{z:\forall x.\exists y.\phi (x,y,z)\}\,}$

以来${\displaystyle \exists y.\phi (x,y,z)}$は SAT のインスタンスとみなすことができ (クック・レヴィンの定理による)、回路が存在する${\displaystyle D_{n}}$、 に応じて${\displaystyle n=|z|}$、 Lを定義する式は以下と同等である。

さらに、存在量化を用いて回路を推測することができる。

明らかに（1）は（2）を意味する。もし（1）が偽ならば、${\displaystyle \neg \exists y.\phi (x,y,z)}$この場合、どの回路Dも割り当てを行う出力をすることはできません。${\displaystyle \phi (x,D(x,z),z)\;}$真実。

証明によると、$\displaystyle \Pi _{2}}$セット${\displaystyle L}$は$\displaystyle \Sigma _{2}}$。

さらに、$\displaystyle \Pi _{2}}$式が真であれば、回路D は任意のxに対して機能します。$\displaystyle \Pi _{2}}$式が偽の場合、式(1)を偽にするxは、あらゆる回路に対して機能します。この特性は、より強力な崩壊、すなわちS ^P ₂複雑性クラス(つまり$\displaystyle \Pi _{2}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}}$これはセングプタによって観察された。^{[ 2 ]}

Kannanの定理^{[ 4 ]}は、任意の固定されたkに対して言語が存在することを述べている。${\displaystyle L}$で$\displaystyle \Sigma _{2}}$、これはSIZE (n ^k ) には含まれません (これは、${\displaystyle \Sigma _{2}\not \subseteq {\mathsf {P/poly}}}$これは現在オープンで、任意のkに対してSIZE (n ^k )に含まれない単一の言語が存在すると述べています。これは単純な回路の下限です。

証明の概要：

言語が存在する${\displaystyle L\in \Sigma _{4}-{\mathsf {SIZE}}(n^{k})}$（証明には対角線法が用いられています。）次の2つのケースを考えてみましょう。

• もし${\displaystyle {\mathsf {SAT}}\notin {\mathsf {P/poly}}}$それから${\displaystyle {\mathsf {SAT}}\notin {\mathsf {SIZE}}(n^{k})}$そして定理が証明された。
• もし${\displaystyle {\mathsf {SAT}}\in {\mathsf {P/poly}}}$そして、カープ・リプトンの定理により、$\displaystyle \Sigma _{4}=\Sigma _{2}}$そのため${\displaystyle L\in \Sigma _{2}-{\mathsf {SIZE}}(n^{k})}$。

カープ・リプトンの定理のより強力なバージョンは、カンナンの定理を次のように強化する：任意のkに対して、言語が存在する${\displaystyle L\in {\mathsf {S}}_{2}^{P}-{\mathsf {SIZE}}(n^{k})}$。

PPは含まれていないことも知られています${\displaystyle {\mathsf {SIZE}}(n^{k})}$これはヴィノドチャンドランによって証明された。^{[ 5 ]}証明: ^{[ 6 ]}

• もし${\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {P/poly}}}$それから${\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {SIZE}}(n^{k})}$。
• さもないと、${\displaystyle {\mathsf {P^{\#P}}}\subseteq {\mathsf {P/poly}}}$。 以来

${\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PP}}\supseteq {\mathsf {MA}}}$( MA所有)

$\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PH}}\supseteq \Sigma _{2}\supseteq {\mathsf {MA}}}$（戸田の定理とMAの性質による）

${\displaystyle {\mathsf {P^{\#P}}}={\mathsf {MA}}}$（永続的なインタラクティブプロトコルを使用するという仮定に基づく。P /polyを参照）

包含関係は等式であり、${\displaystyle {\mathsf {PP}}=\Sigma _{2}\not \subseteq {\mathsf {SIZE}}(n^{k})}$カンナンの定理による。

• Karp, RM ; Lipton, RJ (1980)、「非均一複雑度クラスと均一複雑度クラスの関連性」、第12回ACM理論計算シンポジウム議事録、pp. 302–309、doi : 10.1145/800141.804678、ISBN  0-89791-017-6S2CID 1458043​ 。

• カープ, RM ; RJ リプトン(1982)、「アドバイスを受けるチューリング マシン」、L'Enseignement Mathématique、28 : 191–209、doi : 10.5169/seals-52237。