多項式階層

計算複雑性理論において、多項式階層（多項式時間階層とも呼ばれる）は、クラスNPとco-NPを一般化する複雑性クラスの階層である。^[1]階層内の各クラスはPSPACE内に含まれます。階層は、オラクルマシンまたは交互チューリングマシンを使用して定義できます。これは、数理論理学の算術階層と解析階層のリソース制限付き対応物です。階層内のクラスの和集合はPHで表されます。

階層内のクラスには、量指定子の順序に制限がある式に対して量指定ブール式が成り立つかどうかを尋ねる完全な問題（多項式時間削減に関して）があります。階層内の同じレベルまたは連続するレベルのクラス間の等価性は、そのレベルへの階層の「崩壊」を意味することが知られています。

多項式階層のクラスには同等の定義が複数あります。

多項式階層のオラクル定義では、次のように定義します。

${\displaystyle \Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},}$

ここでPは多項式時間で解ける決定問題の集合である。i ≥ 0に対して定義する。

${\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}}$

${\displaystyle \Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}}$

${\displaystyle \Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Sigma _{i}^{\mathsf {P}}}}$

ここで、はクラスAの完全な問題に対するオラクルによって拡張されたチューリングマシンによって多項式時間で解ける決定問題の集合です。クラスとも同様の定義になります。たとえば、、およびは、NP完全な問題に対するオラクルを備えた決定性チューリングマシンによって多項式時間で解ける問題のクラスです。^[2]${\displaystyle {\mathsf {P}}^{\rm {A}}}$${\displaystyle {\mathsf {NP}}^{\rm {A}}}$${\displaystyle {\mathsf {coNP}}^{\rm {A}}}$${\displaystyle \Sigma _{1}^{\mathsf {P}}={\mathsf {NP}},\Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}}$${\displaystyle \Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}}$

多項式階層の存在論的/普遍的定義では、Lを言語（つまり、決定問題、{0,1} ^*のサブセット）とし、pを多項式とし、次のように定義する。

${\displaystyle \exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},}$

ここで、はバイナリ文字列xとwのペアを1 つのバイナリ文字列として標準的にエンコードしたものです。言語L は、文字列の順序付きペアの集合を表します。最初の文字列x はのメンバーであり、2 番目の文字列wは、 xが のメンバーであることを証明する「短い」( ) 証拠です。言い換えると、となる短い証拠w が存在する場合のみ となります。同様に、次のように定義します。 ${\displaystyle \langle x,w\rangle \in \{0,1\}^{*}}$${\displaystyle \exists ^{p}L}$${\displaystyle |w|\leq p(|x|)}$${\displaystyle \exists ^{p}L}$${\displaystyle x\in \exists ^{p}L}$${\displaystyle \langle x,w\rangle \in L}$

${\displaystyle \forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}}$

ド・モルガンの法則が成り立つことに注意してください:および、ここでL ^{c は}Lの補数です。 ${\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}}$${\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}$

Cを言語のクラスと する。これらの演算子を、定義によって言語のクラス全体に作用するように拡張する。

${\displaystyle \exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}}$

${\displaystyle \forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}}$

ここでも、ド・モルガンの法則が成り立ちます。また、。 ${\displaystyle {\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}$${\displaystyle {\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}$${\displaystyle {\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}$

クラスNPとco-NPは、 、 、と定義できます。ここで、Pはすべての実行可能（多項式時間）決定可能な言語のクラスです。多項式階層は再帰的に次のように定義できます。 ${\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}}$${\displaystyle {\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}}$

${\displaystyle \Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}}$

${\displaystyle \Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}}$

${\displaystyle \Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}}$

、および に注意してください。 ${\displaystyle {\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}}$${\displaystyle {\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}}$

この定義は、多項式階層と算術階層の密接な関係を反映しており、RとRE はそれぞれPとNPに類似した役割を果たします。解析階層も同様の方法で定義され、実数のサブセットの階層を与えます。

交代チューリングマシンは、非最終状態が存在状態と普遍状態に分割された非決定性チューリングマシンです。現在の構成から最終的に受け入れるには、存在状態にあり、最終的に受け入れる構成に遷移できる場合、または普遍状態にあり、すべての遷移が最終的に受け入れる構成である場合、または受け入れ状態にある場合が必要です。^[3]

を、初期状態が存在状態であり、マシンが取ることができるすべてのパスが存在状態と普遍状態の間で最大k -1回入れ替わるような、多項式時間で交代チューリングマシンによって受け入れられる言語のクラスと定義します。同様に定義しますが、初期状態は普遍状態です。^[4]${\displaystyle \Sigma _{k}^{\mathsf {P}}}$${\displaystyle \Pi _{k}^{\mathsf {P}}}$

存在状態と普遍状態の間のスワップが最大でk -1回であるという要件を省略し、交代チューリングマシンが多項式時間で動作することだけを要求すると、クラスAPの定義が得られ、これはPSPACEに等しくなります。^[5]

多項式階層内のすべてのクラスの和集合が複雑性クラスPHです。

定義は以下の関係を暗示します:

${\displaystyle \Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}}$

${\displaystyle \Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}}$

${\displaystyle \Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}}$

算術階層や解析階層では包含が適切であることが知られていますが、これらの包含が適切であるかどうかは未解決の問題です。ただし、すべてが適切であると広く信じられています。、または のいずれかの場合、階層はレベル k に縮小します。すべての、に対して。^[6]特に、未解決の問題に関連する次の意味があります。 ${\displaystyle \Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}}$${\displaystyle \Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}}$${\displaystyle i>k}$${\displaystyle \Sigma _{i}^{\mathsf {P}}=\Sigma _{k}^{\mathsf {P}}}$

• P = NPであるのは、 P = PHの場合に限ります。 ^[7]
• NP = co-NPの場合、NP = PHです。( co-NPは です。)${\displaystyle \Pi _{1}^{\mathsf {P}}}$

NP = PHの場合は、PHが第 2 レベルに崩壊するとも呼ばれます。P = NPの場合は、PHがPに崩壊することに対応します。

コンピュータサイエンスにおける未解決の問題:

⁠ ⁠${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {NP}}}$

(コンピュータサイエンスにおける未解決の問題)

第一レベルへの崩壊の問題は、一般的に非常に難しいと考えられています。ほとんどの研究者は、第二レベルへの崩壊さえも信じていません。

コンピュータサイエンスにおける未解決の問題:

⁠ ⁠${\displaystyle {\mathsf {PH}}{\overset {?}{=}}{\mathsf {PSPACE}}}$

(コンピュータサイエンスにおける未解決の問題)

多項式階層は、指数階層と算術階層の類似物です（複雑さははるかに低くなります） 。

PH がPSPACE内に含まれていることは分かっていますが、2つのクラスが等しいかどうかは分かっていません。この問題の有用な定式化の1つは、有限構造上の2階論理が関係の関係（つまり、2階変数）上の推移閉包演算子の追加によって追加のパワーを獲得しない場合にのみ、 PH = PSPACE である、というものです。 ^[8]

多項式階層に完全な問題がある場合、その階層には有限個の異なるレベルしかありません。PSPACE完全な問題が存在するため、PSPACE = PHの場合、PSPACE完全な問題はあるkに対して完全な問題になるため、多項式階層は必ず崩壊することがわかります。^[9]${\displaystyle \Sigma _{k}^{\mathsf {P}}}$

多項式階層の各クラスには、-完全問題（多項式時間の多対一還元の下で完全な問題）が含まれます。さらに、多項式階層の各クラスは-還元の下で閉じています。つまり、階層内のクラスCと言語について、であればも成り立ちます。これら 2 つの事実を合わせると、 がに対して完全問題である場合、 であり、 であることが示されます。たとえば、 です。言い換えると、言語がCの何らかの神託に基づいて定義されている場合、その言語はCに対する完全問題に基づいて定義されていると想定できます。したがって、完全問題は、それが完全であるクラスの「代表」として機能します。 ${\displaystyle \leq _{\rm {m}}^{\mathsf {P}}}$${\displaystyle \leq _{\rm {m}}^{\mathsf {P}}}$${\displaystyle L\in {\mathcal {C}}}$${\displaystyle A\leq _{\rm {m}}^{\mathsf {P}}L}$${\displaystyle A\in {\mathcal {C}}}$${\displaystyle K_{i}}$${\displaystyle \Sigma _{i}^{\mathsf {P}}}$${\displaystyle \Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}}$${\displaystyle \Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}}$${\displaystyle \Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}}$

Sipser -Lautemann の定理は、BPPクラスが多項式階層の第 2 レベルに含まれていることを述べています。

カンナンの定理は、任意のkに対して、SIZE (n ^k )に含まれないことを述べています。 ${\displaystyle \Sigma _{2}}$

戸田の定理は、多項式階層が P ^#Pに含まれていることを述べています。

• 有効期限
• 指数階層
• 算術階層

1. アローラ、サンジーヴ、バラク、ボアズ (2009)。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4セクション1.4「文字列としてのマシンと汎用チューリングマシン」および 1.7「定理 1.9 の証明」
2. AR MeyerとLJ Stockmeyer。「平方化を伴う正規表現の同値性問題には指数空間が必要」。1972 年、第 13 回 IEEEスイッチングおよびオートマトン理論シンポジウムの議事録、125 ～ 129 ページ。多項式階層を導入した論文。
3. LJ Stockmeyer . 多項式時間階層.理論計算機科学, 第3巻, pp. 1–22, 1976年.
4. C. Papadimitriou . 計算複雑性. Addison-Wesley, 1994. 第17章多項式階層、pp. 409–438。
5. Michael R. GareyとDavid S. Johnson (1979)。コンピュータと扱いにくさ: NP 完全性理論のガイド。WH Freeman。ISBN 0-7167-1045-5。セクション7.2: 多項式階層、pp. 161–167。