Computer science concept
計算複雑性理論 において 、 多項式階層 （ 多項式時間階層 とも呼ばれる）は、 クラス NP と co-NP を一般化する複雑性クラス の 階層 である。 [1] 階層内の各クラスは PSPACE に含まれます。この階層は、オラクルマシン または 交代チューリングマシン を用いて定義できます。これは、 数理論理学 における 算術階層 と 解析階層 の、リソース制限された対応物です。階層内のクラスの和集合は PH で表されます 。
階層構造内のクラスは、（多項式時間縮約 に関して） 量化ブール論理式が 、量化子の順序に制限のある論理式に対して成立するかどうかを問う完全な問題を抱えている 。階層構造内の同一レベルまたは連続するレベルにあるクラス間の等価性は、そのレベルまでの階層構造の「崩壊」を意味することが知られている。
定義 多項式階層のクラスには同等の定義が複数存在します。
Oracleの定義 多項式階層のオラクル定義では、次のように定義する。
Δ 0 P := Σ 0 P := Π 0 P := P , {\displaystyle \Delta _{0}^{\mathrm {P} }:=\Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P} ,} ここで Pは 多項式時間 で解ける 決定問題 の集合である 。そしてi ≥ 0に対して定義する。
Δ i + 1 P := P Σ i P {\displaystyle \Delta _{i+1}^{\mathrm {P} }:=\mathrm {P} ^{\Sigma _{i}^{\mathrm {P} }}} Σ i + 1 P := N P Σ i P {\displaystyle \Sigma _{i+1}^{\mathrm {P} }:=\mathrm {NP} ^{\Sigma _{i}^{\mathrm {P} }}} Π i + 1 P := c o N P Σ i P {\displaystyle \Pi _{i+1}^{\mathrm {P} }:=\mathrm {coNP} ^{\Sigma _{i}^{\mathrm {P} }}} ここで、はクラスAのある完全問題に対する オラクル を付加した チューリングマシン によって多項式時間で解ける 決定問題 の集合である 。クラス とも 同様の定義となる。例えば、、 およびは、 あるNP完全問題に対するオラクルを付加した決定性チューリングマシンによって多項式時間で解ける問題のクラスである。 [2] P A {\displaystyle \mathrm {P} ^{\rm {A}}} N P A {\displaystyle \mathrm {NP} ^{\rm {A}}} c o N P A {\displaystyle \mathrm {coNP} ^{\rm {A}}} Σ 1 P = N P , Π 1 P = c o N P {\displaystyle \Sigma _{1}^{\mathrm {P} }=\mathrm {NP} ,\Pi _{1}^{\mathrm {P} }=\mathrm {coNP} } Δ 2 P = P N P {\displaystyle \Delta _{2}^{\mathrm {P} }=\mathrm {P^{NP}} }
多項式階層の存在論的/普遍的定義では、 Lを 言語 （つまり、 決定問題、{0,1} * の部分集合） とし 、 pを 多項式 とし、 次のように定義する。
∃ p L := { x ∈ { 0 , 1 } ∗ | ( ∃ w ∈ { 0 , 1 } ≤ p ( | x | ) ) ⟨ x , w ⟩ ∈ L } , {\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\},} ここで、は2進文字列 x と w のペアを 単一の2進文字列として符号化した標準的な表現である。言語 Lは 、文字列の順序付きペアの集合を表す。最初の文字列 x は のメンバーで あり、2番目の文字列 wは x が のメンバーであることを証明する 「短い」（ ）証拠である 。言い換えれば、となる短い証拠 w が存在する場合、かつ その場合のみである 。同様に、 ⟨ x , w ⟩ ∈ { 0 , 1 } ∗ {\displaystyle \langle x,w\rangle \in \{0,1\}^{*}} ∃ p L {\displaystyle \exists ^{p}L} | w | ≤ p ( | x | ) {\displaystyle |w|\leq p(|x|)} ∃ p L {\displaystyle \exists ^{p}L} x ∈ ∃ p L {\displaystyle x\in \exists ^{p}L} ⟨ x , w ⟩ ∈ L {\displaystyle \langle x,w\rangle \in L}
∀ p L := { x ∈ { 0 , 1 } ∗ | ( ∀ w ∈ { 0 , 1 } ≤ p ( | x | ) ) ⟨ x , w ⟩ ∈ 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 の補数です 。 ( ∃ p L ) c = ∀ p L c {\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}} ( ∀ p L ) c = ∃ p L c {\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}
Cを 言語のクラスとする。これらの演算子を、定義により言語のクラス全体に作用するように拡張する 。
∃ P C := { ∃ p L | p is a polynomial and L ∈ C } {\displaystyle \exists ^{\mathrm {P} }{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}} ∀ P C := { ∀ p L | p is a polynomial and L ∈ C } {\displaystyle \forall ^{\mathrm {P} }{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}} また、ド・モルガンの法則は成り立ちます。 また 、 です 。 c o ∃ P C = ∀ P c o C {\displaystyle \mathrm {co} \exists ^{\mathrm {P} }{\mathcal {C}}=\forall ^{\mathrm {P} }\mathrm {co} {\mathcal {C}}} c o ∀ P C = ∃ P c o C {\displaystyle \mathrm {co} \forall ^{\mathrm {P} }{\mathcal {C}}=\exists ^{\mathrm {P} }\mathrm {co} {\mathcal {C}}} c o C = { L c | L ∈ C } {\displaystyle \mathrm {co} {\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}
NP クラスと co-NP クラスは、 Pが すべての実行可能（多項式時間）決定可能言語のクラスであるとして、 、 、と 定義できる 。多項式階層は再帰的に次のように定義できる。 N P = ∃ P P {\displaystyle \mathrm {NP} =\exists ^{\mathrm {P} }\mathrm {P} } c o N P = ∀ P P {\displaystyle \mathrm {coNP} =\forall ^{\mathrm {P} }\mathrm {P} }
Σ 0 P := Π 0 P := P {\displaystyle \Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P} } Σ k + 1 P := ∃ P Π k P {\displaystyle \Sigma _{k+1}^{\mathrm {P} }:=\exists ^{\mathrm {P} }\Pi _{k}^{\mathrm {P} }} Π k + 1 P := ∀ P Σ k P {\displaystyle \Pi _{k+1}^{\mathrm {P} }:=\forall ^{\mathrm {P} }\Sigma _{k}^{\mathrm {P} }} 、および に 注意してください 。 N P = Σ 1 P {\displaystyle \mathrm {NP} =\Sigma _{1}^{\mathrm {P} }} c o N P = Π 1 P {\displaystyle \mathrm {coNP} =\Pi _{1}^{\mathrm {P} }}
この定義は、多項式階層と 算術階層 の密接な関係を反映しており、 R と RE はそれぞれ P と NP と同様の役割を果たします 。 解析階層も同様の方法で定義され、 実数 の部分集合の階層を与えます 。
交代チューリングマシンの定義 交代型 チューリングマシンは 、非決定性チューリングマシンであり、非最終状態が存在状態と普遍状態に分割されている。交代型チューリングマシンが現在の状態から最終的に受理するとは、以下のいずれかの条件を満たす場合である：存在状態にあり、最終的に受理可能な状態へ遷移できる場合、または、普遍状態にあり、すべての遷移が最終的に受理可能な状態へ遷移する場合、または、受理状態にある場合。 [3]
を、多項式時間で交代チューリングマシンが受理する言語のクラスと 定義する。このクラスにおいて、初期状態は存在状態であり、マシンが取り得るすべてのパスは、存在状態と普遍状態の間で最大 k -1回入れ替わる。 同様に定義するが、初期状態は普遍状態である。 [4] Σ k P {\displaystyle \Sigma _{k}^{\mathrm {P} }} Π k P {\displaystyle \Pi _{k}^{\mathrm {P} }}
存在状態と普遍状態の間のスワップが最大でk -1回であるという要件を省略し、交代チューリングマシンが多項式時間で動作することだけを要求すると、クラス AP の定義が得られ、これは PSPACE に等しい 。 [5]
多項式階層におけるクラス間の関係 多項式時間階層に相当する可換図。矢印は包含を表す。 多項式階層内のすべてのクラスの結合は複雑性クラス PH です。
定義は次の関係を意味します:
Σ i P ⊆ Δ i + 1 P ⊆ Σ i + 1 P {\displaystyle \Sigma _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Sigma _{i+1}^{\mathrm {P} }} Π i P ⊆ Δ i + 1 P ⊆ Π i + 1 P {\displaystyle \Pi _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Pi _{i+1}^{\mathrm {P} }} Σ i P = c o Π i P {\displaystyle \Sigma _{i}^{\mathrm {P} }=\mathrm {co} \Pi _{i}^{\mathrm {P} }} 算術階層や解析階層とは異なり、その包含が適切であることが知られているが、これらの包含が適切であるかどうかは未解決の問題である。ただし、すべてが適切であると広く信じられている。 、または のいずれかがある場合 、階層は レベル k に縮退する ：すべての 、について 。 [6] 特に、未解決問題に関連する以下の含意がある。 Σ k P = Σ k + 1 P {\displaystyle \Sigma _{k}^{\mathrm {P} }=\Sigma _{k+1}^{\mathrm {P} }} Σ k P = Π k P {\displaystyle \Sigma _{k}^{\mathrm {P} }=\Pi _{k}^{\mathrm {P} }} i > k {\displaystyle i>k} Σ i P = Σ k P {\displaystyle \Sigma _{i}^{\mathrm {P} }=\Sigma _{k}^{\mathrm {P} }}
P = NPで あるべきとき、そしてそのときに限り、 P = PH である。 [7] NP = co-NP の場合 、 NP = PH です。( co-NP は です 。) Π 1 P {\displaystyle \Pi _{1}^{\mathrm {P} }} NP = PH の場合は、 PH が 第2レベル に 崩壊する とも呼ばれます。P = NP の場合は、 PH が P に 崩壊することに対応します 。
コンピュータサイエンスにおける未解決問題
P = ? N P {\displaystyle \mathrm {P} {\overset {?}{=}}\mathrm {NP} } 第一レベルへの崩壊という問題は、一般的に非常に難しいと考えられています。ほとんどの研究者は、第二レベルへの崩壊さえも信じていません。
他のクラスとの関係 コンピュータサイエンスにおける未解決問題
P H = ? P S P A C E {\displaystyle \mathrm {PH} {\overset {?}{=}}\mathrm {PSPACE} } P 、 NP 、 co-NP 、 BPP 、 P/poly 、PH、 PSPACE を含む複雑性クラスの ハッセ図 多項式階層は、 指数階層 と 算術階層 の類似物です（複雑さははるかに低くなります） 。
PH がPSPACE に含まれることは分かっている が、2つのクラスが等しいかどうかは分かっていない。この問題の有用な再定式化の一つは、 有限構造上の二階述語論理 が、関係の関係（すなわち二階変数）上の 推移閉包 演算子を追加しても、追加のパワーを得ない場合に限り、PH = PSPACE となることである。 [8]
多項式階層に 完全問題 が存在する場合、その階層は有限個の異なるレベルしか持たない。PSPACE 完全問題が存在するため、PSPACE = PHならば多項式階層は必ず崩壊することがわかる。なぜなら、PSPACE完全問題はある k に対して -完全問題となるからである 。 [9] Σ k P {\displaystyle \Sigma _{k}^{\mathrm {P} }}
多項式階層の各クラスには 、 -完全問題（多項式時間の多対一縮約に関して完全な問題）が含まれます。さらに、多項式階層の各クラスは -縮約 に関して閉じて います。つまり、階層内の クラス C と言語 について、 で あれば も成り立ちます。これら2つの事実を合わせると、 が について完全問題である場合 、 、 が成り立ちます 。例えば、 です 。言い換えれば、言語が Cの何らかの神託に基づいて定義されている場合、その言語は C の完全問題に基づいて定義されていると仮定できます 。したがって、完全問題は、それが完全であるクラスの「代表」として機能します。 ≤ m P {\displaystyle \leq _{\rm {m}}^{\mathrm {P} }} ≤ m P {\displaystyle \leq _{\rm {m}}^{\mathrm {P} }} L ∈ C {\displaystyle L\in {\mathcal {C}}} A ≤ m P L {\displaystyle A\leq _{\rm {m}}^{\mathrm {P} }L} A ∈ C {\displaystyle A\in {\mathcal {C}}} K i {\displaystyle K_{i}} Σ i P {\displaystyle \Sigma _{i}^{\mathrm {P} }} Σ i + 1 P = N P K i {\displaystyle \Sigma _{i+1}^{\mathrm {P} }=\mathrm {NP} ^{K_{i}}} Π i + 1 P = c o N P K i {\displaystyle \Pi _{i+1}^{\mathrm {P} }=\mathrm {coNP} ^{K_{i}}} Σ 2 P = N P S A T {\displaystyle \Sigma _{2}^{\mathrm {P} }=\mathrm {NP} ^{\mathrm {SAT} }}
シプサー・ローテマンの定理 : 。 B P P ⊂ Σ 2 P ∩ Π 2 P {\displaystyle \mathrm {BPP} \subset \Sigma _{2}^{\mathrm {P} }\cap \Pi _{2}^{\mathrm {P} }} カンナンの定理 ： かどうかは未解決の問題である 。 ∀ k , Σ 2 ⊄ S I Z E ( n k ) {\displaystyle \forall k,\Sigma _{2}\not \subset \mathrm {SIZE} (n^{k})} Σ 2 ⊄ ⋃ k S I Z E ( n k ) = P / p o l y {\displaystyle \Sigma _{2}\not \subset \bigcup _{k}\mathrm {SIZE} (n^{k})=\mathrm {P/poly} } 戸田の定理 ： 。 P H ⊂ P # P {\displaystyle \mathrm {PH} \subset \mathrm {P} ^{\mathrm {\#P} }} 量子コンピュータ によって多項式時間で解ける問題のクラスである BQPは PHに含まれない という証拠がいくつかあります。しかし、PHはBQPに含まれないと考えられています。 [10] = [11]
問題 回路の最小化 は 、自然言語における問題の一例です 。数値 kと ブール関数 f を計算する 回路 A が与えられたとき、同じ関数 f を計算するゲート数が最大 k の 回路が存在するかどうかを判定します。C は すべてのブール回路の集合とします。言語 Σ 2 P {\displaystyle \Sigma _{2}^{\mathrm {P} }} L = { ⟨ A , k , B , x ⟩ ∈ C × N × C × { 0 , 1 } ∗ | B has at most k gates, and A ( x ) = B ( x ) } {\displaystyle L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\text{ has at most }}k{\text{ gates, and }}A(x)=B(x)\right.\right\}} 多項式時間で決定可能である。言語
C M = { ⟨ A , k ⟩ ∈ C × N | there exists a circuit B with at most k gates such that A and B compute the same function } {\displaystyle {\mathit {CM}}=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\text{there exists a circuit }}B{\text{ with at most }}k{\text{ gates }}\\{\text{ such that }}A{\text{ and }}B{\text{ compute the same function}}\end{matrix}}\right.\right\}} は回路最小化言語です。 なぜなら、 L は多項式時間で決定可能であり、 が与えられた 場合、 すべての 入力 x に対してとなる 回路 B が存在する 場合のみ、 となるから です 。 C M ∈ Σ 2 P ( = ∃ P ∀ P P ) {\displaystyle {\mathit {CM}}\in \Sigma _{2}^{\mathrm {P} }(=\exists ^{\mathrm {P} }\forall ^{\mathrm {P} }\mathrm {P} )} ⟨ A , k ⟩ {\displaystyle \langle A,k\rangle } ⟨ A , k ⟩ ∈ C M {\displaystyle \langle A,k\rangle \in {\mathit {CM}}} ⟨ A , k , B , x ⟩ ∈ L {\displaystyle \langle A,k,B,x\rangle \in L} の完全な問題は、 k – 1 個 の量指定子の交替を伴う量指定ブール式 （ QBF k または QSAT k と略記）の充足可能性である。これは 、 のブール充足可能性問題 の バージョンである。この問題では、 変数が k 個の集合 X 1 , ..., X k に分割されたブール式f が与えられる 。以下が真であるかどうかを判定する必要がある
。 Σ k P {\displaystyle \Sigma _{k}^{\mathrm {P} }} Σ k P {\displaystyle \Sigma _{k}^{\mathrm {P} }} ∃ X 1 ∀ X 2 ∃ X 3 … f {\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\ldots f} つまり、 X 1 の変数への値の割り当てがあり、 X 2 のすべての値の割り当てに対して、 X 3 の変数への値の割り当てが存在する 、… f は真ですか？上記の変形は に対して完全 です。最初の量指定子が「すべてに対して」、2番目が「存在する」などである変形は に対して完全です。各言語は、 k – 1 個の交替制約を取り除いた問題、つまり PSPACE 完全問題 TQBF のサブセットです 。 Σ k P {\displaystyle \Sigma _{k}^{\mathrm {P} }} Π k P {\displaystyle \Pi _{k}^{\mathrm {P} }} 多項式階層の 2 番目以降のレベルに対して完全であることが知られている Garey/Johnson スタイルの問題のリストは、この概要に記載されています。
参照
参考文献
一般的な参考文献 アローラ、サンジーヴ、バラク、ボアズ（2009年）『複雑性理論：現代的アプローチ』ケンブリッジ大学出版局、 ISBN 978-0-521-42426-4 セクション1.4 「文字列としてのマシンと汎用チューリングマシン」およびセクション1.7「定理1.9の証明」 AR Meyer と LJ Stockmeyer . 平方化を伴う正規表現の同値性問題は指数空間を必要とする. 第13回IEEE スイッチング・オートマトン理論シンポジウム 論文集, pp. 125–129, 1972. 多項式階層を導入した論文。 LJ Stockmeyer . 多項式時間階層. 理論計算機科学 , 第3巻, pp. 1-22, 1976. C. パパディミトリウ著 『計算複雑性』アディソン・ウェズレー社、1994年。第17章 多項式階層 、pp.409–438。 マイケル・R・ギャリー 、 デイビッド・S・ジョンソン （1979年） 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』 WHフリーマン著、 ISBN 0-7167-1045-5 。 セクション7.2: 多項式階層、pp. 161–167。
引用 ^ アローラとバラク、2009、pp.97 ^ 多項式時間階層における完全性概要、M. Schaefer、C. Umans ^ アローラとバラク、pp.99–100 ^ アローラとバラク、pp.100 ^ アローラとバラク、pp.100 ^ アローラとバラク、2009、定理5.4 ^ Hemaspaandra, Lane (2018). 「17.5 計算量クラス」. Rosen, Kenneth H. (編). 『離散数学と組合せ数学ハンドブック』 . 『離散数学とその応用（第2版）』. CRC Press. pp. 1308– 1314. ISBN 9781351644051 。 ^ フェラロッティ、フラヴィオ;ヴァン・デン・ブッシュ、ヤン。ヴィルテマ、ジョニ (2018)。 「二次推移閉包ロジック内の表現力」。 DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 。ダグシュトゥール城 - ライプニッツ情報センター。 土井 ： 10.4230/LIPIcs.CSL.2018.22 。 S2CID 4903744。 ^ アローラとバラク、2009年、主張5.5 ^ Aaronson, Scott (2009). 「BQPと多項式階層」. Proc. 42nd Symposium on Theory of Computing (STOC 2009) . Association for Computing Machinery . pp. 141– 150. arXiv : 0910.4698 . doi :10.1145/1806689.1806711. ECCC TR09-104. ^ ハートネット、ケビン（2018年6月21日）「ついに量子コンピュータだけが解決できる問題が出現」 Quanta Magazine 。
実現可能と考えられる 実行不可能と疑われる 実現不可能とみなされる その他の複雑性クラス クラス階層 クラスのファミリー
