Warning: Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297
Warning: Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660
Warning: session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834
Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126
Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127
Warning: session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133
Warning: session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 https:///mymemo.xyz/wiki/api.php?action=feedcontributions&feedformat=atom&user=175.177.5.26miniwiki - 利用者の投稿記録 [ja]2024-06-17T16:44:02Z利用者の投稿記録MediaWiki 1.31.0多項式階層2018-02-20T00:07:03Z<p>175.177.5.26: 読みづらい式に改行を追加</p>
<hr />
<div>'''多項式階層'''（たこうしきかいそう、{{lang-en-short|Polynomial hierarchy}}）は、[[計算量理論]]における計算量の階層であり、[[神託機械]]を使って [[P (計算量理論)|'''P''']]、'''[[NP]]'''、[[Co-NP|co-'''NP''']] を一般化させて定義されるものである。<br />
<br />
== 定義 ==<br />
多項式階層をなすクラス群の定義はいくつか存在する。<br />
<br />
<ol><br />
<li><br />
多項式階層は神託機械を使って次のように定義する。<br />
<br />
{{Indent|<math>\Delta_0^{\rm P} := \Sigma_0^{\rm P} := \Pi_0^{\rm P} := \mbox{P},</math>}}<br />
<br />
ここで、[[P (計算量理論)|'''P''']] は[[多項式時間]]内で解ける[[決定問題]]の集合である。i &ge; 0 については、次のように定義する。<br />
{{Indent|<br />
<math>\Delta_{i+1}^{\rm P} := \mbox{P}^{\Sigma_i^{\rm P}}</math><br /><br />
<math>\Sigma_{i+1}^{\rm P} := \mbox{NP}^{\Sigma_i^{\rm P}}</math><br /><br />
<math>\Pi_{i+1}^{\rm P} := \mbox{coNP}^{\Sigma_i^{\rm P}}</math><br />
}}<br />
ここで、A<sup>B</sup> はクラス A の[[チューリングマシン]]にクラス B の何らかの問題を解く[[神託機械|神託]]を付加して強化したもので解ける[[決定問題]]の集合である。例えば、<math> \Sigma_1^{\rm P} = {\rm NP}, \Pi_1^{\rm P} = {\rm coNP} </math> であり、<math> \Delta_2^{\rm P} = {\rm P^{NP}} </math> は '''NP''' に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。<br />
</li><li><br />
多項式階層の存在/全称的定義のため、<math>L</math> を[[形式言語]]（すなわち、一種の[[決定問題]]であり、{0,1}<sup>*</sup> の部分集合である）、<math>p</math> を[[多項式]]とし、次のように定義する。<br />
<br />
{{Indent|<math> \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\}, </math>}}<br />
<br />
ここで、<math>\langle x,w \rangle \in \{0,1\}^*</math> は2進文字列 ''x'' と ''w'' を1つの2進文字列にする何らかの標準的符号化である。''L'' は文字列の順序対の集合を表しており、第一の文字列 ''x'' は <math>\exists^p L</math> の元で、第二の文字列 ''w'' は ''x'' が <math>\exists^p L</math> の元であることを示す短い (<math>|w| \leq p(|x|) </math>) 証拠である。言い換えれば、<math>x \in \exists^p L</math> は、<math> \langle x,w \rangle \in L </math> であるような短い証拠 ''w'' が存在することと同値である。同様に次のように定義する。<br />
<br />
{{Indent|<math> \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\} </math>}}<br />
<br />
ドモルガンの定理により、<math> \left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c} </math> かつ <math> \left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c} </math> であり、ここで ''L''<sup>c</sup> は ''L'' の補集合である。ここで <math>\mathcal{C}</math> を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。<br />
<br />
{{Indent|<math>\exists^{\rm P} \mathcal{C} := \left\{\exists^p L \ | \ p \mbox{ is a polynomial and } L \in \mathcal{C} \right\}</math><br /><br />
<math>\forall^{\rm P} \mathcal{C} := \left\{\forall^p L \ | \ p \mbox{ is a polynomial and } L \in \mathcal{C} \right\}</math>}}<br />
<br />
再びドモルガンの定理により、<math> {\rm co} \exists^{\rm P} \mathcal{C} = \forall^{\rm P} {\rm co} \mathcal{C} </math> かつ <math> {\rm co} \forall^{\rm P} \mathcal{C} = \exists^{\rm P} {\rm co} \mathcal{C} </math> であり、ここで <math>{\rm co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}</math> である。クラス '''[[NP]]''' と [[Co-NP|co-'''NP''']] は <math> {\rm NP} = \exists^{\rm P} {\rm P} </math> と <math> {\rm coNP} = \forall^{\rm P} {\rm P} </math> と定義され、ここで '''[[P (計算複雑性理論)|P]]''' は（多項式時間で）適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。<br />
{{Indent|<br />
<math> \Sigma_0^{\rm P} := \Pi_0^{\rm P} := {\rm P} </math><br />
<br />
<math> \Sigma_{k+1}^{\rm P} := \exists^{\rm P} \Pi_k^{\rm P} </math><br />
<br />
<math> \Pi_{k+1}^{\rm P} := \forall^{\rm P} \Sigma_k^{\rm P} </math><br />
}}<br />
なお、<math> {\rm NP} = \Sigma_1^{\rm P} </math> であり、かつ <math> {\rm coNP} = \Pi_1^{\rm P} </math> である。この定義は多項式階層と[[算術的階層]]の密接な関連を反映しており、後者で '''[[帰納言語|DEC]]''' と '''[[帰納的可算言語|CE]]''' が果たした役割をそれぞれ '''[[P (計算量理論)|P]]''' と '''[[NP]]''' が果たしている。同様の方法で、実数の部分集合の階層として[[解析的階層]]が定義される。<br />
</li><li><br />
[[交替性チューリング機械]]を使った等価な定義として、<math>\Sigma_k^{\rm P}</math>（あるいは <math>\Pi_k^{\rm P}</math>）は存在的状態（あるいは全称的状態）から開始する交替性チューリング機械で <math>k</math> 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。<br />
</li><br />
</ol><br />
<br />
== 多項式階層内のクラス間の関係 ==<br />
定義から、次のような関係が成り立つ。<br />
{{Indent|<br />
<math>\Sigma_i^{\rm P} \subseteq \Delta_{i+1}^{\rm P} \subseteq \Sigma_{i+1}^{\rm P}</math><br /><br />
<math>\Pi_i^{\rm P} \subseteq \Delta_{i+1}^{\rm P} \subseteq \Pi_{i+1}^{\rm P}</math><br /><br />
<math>\Sigma_i^{\rm P} = {\rm co}\Pi_{i}^{\rm P}</math><br />
}}<br />
真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか（真部分集合かどうか）は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある ''k'' について <math>\Sigma_k^{\rm P} = \Sigma_{k+1}^{\rm P}</math> すなわち <math>\Sigma_k^{\rm P} = \Pi_{k}^{\rm P}</math> となることを「多項式階層が第 ''k'' 層で潰れる」と言う。もしそうなら全ての <math>i > k</math> について <math>\Sigma_i^{\rm P} = \Sigma_k^{\rm P}</math> となる。特に '''P''' = '''NP''' なら、階層は完全に潰れる。<br />
<br />
多項式階層にある全クラス群の和集合を '''[[PH (計算量理論)|PH]]''' と書く。<br />
<br />
多項式時間階層は、[[指数時間階層]]や算術的階層に似ている。<br />
<br />
'''PH''' が '''[[PSPACE]]''' に包含されることは知られているが、2つのクラスが等しいかどうかは不明である。この問題を言い換えると、'''PH''' = '''PSPACE''' であるならば、[[二階述語論理]]に[[推移閉包]]演算子を追加しても強化されないことになる。<br />
<br />
もし多項式階層が完全問題を含むなら、どこかの層に潰れる。[[PSPACE|'''PSPACE'''完全]]問題は存在するので、'''PSPACE''' = '''PH''' ならば、'''PSPACE'''完全問題が<math>\Sigma_{k}^{\rm P}</math>-完全問題だということになるので、多項式階層は潰れる。<br />
<br />
多項式階層の各層については <math>\leq_{\rm m}^{\rm P}</math>-完全問題（多項式時間多対一還元において完全な問題）がある。さらに、多項式階層の各層は <math>\leq_{\rm m}^{\rm P}</math>-還元において閉じている。つまり、この階層上のあるクラス <math>\mathcal{C}</math> と言語 <math>L \in \mathcal{C}</math> があるとき、<math>A \leq_{\rm m}^{\rm P} L</math> ならば、同時に <math>A \in \mathcal{C}</math> である。これらの事実から、<math>K_i</math> を <math>\Sigma_{i}^{\rm P}</math> の完全問題としたとき、<math>\Sigma_{i+1}^{\rm P} = \left( \Sigma_{i}^{\rm P} \right)^{K_i}</math> と <math>\Pi_{i+1}^{\rm P} = \left( \Pi_{i}^{\rm P} \right)^{K_i^{\rm c}}</math> が成り立つことがわかる。実際、<math>\Sigma_{2}^{\rm P} = {\rm NP}^{\rm SAT}</math> である。言い換えれば、言語を <math>\mathcal{C}</math> に含まれる何らかの神託機械に基づいて定義したとき、それを <math>\mathcal{C}</math> の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。<br />
<br />
== 多項式階層内の問題 ==<br />
<ul><br />
<li><br />
<math>\Sigma_2^P</math> に属する問題の具体例として「回路最小化」問題がある。ある数 ''k'' と[[ブール関数]] ''f'' を計算する回路 ''A'' があるとき、同じ関数 ''f'' を最大 ''k'' 個の論理ゲートで計算できる回路が存在するかを問う決定問題である。<math> \mathcal{C} </math> を全ての論理回路の集合とする。この場合の言語 ''L'' は次のように定義される。<br />
<br />
{{Indent|<math> L = \left\{ \langle A,k,B,x \rangle \in \mathcal{C} \times \mathbb{N} \times \mathcal{C} \times \{0,1\}^* \left| B \mbox{ has at most } k \mbox{ gates, and } A(x)=B(x) \right.\right\} </math>}}<br />
<br />
これは多項式時間で決定可能である。次の言語 ''CM'' が回路最小化問題を表す言語である。<br />
<br />
{{Indent|<math> CM = \left\{ \langle A,k \rangle \in \mathcal{C} \times \mathbb{N} \left| \begin{matrix}\mbox{there exists a circuit } B \mbox{ with at most } k \mbox{ gates } \\ \mbox{ such that } A \mbox{ and } B \mbox{ compute the same function} \end{matrix} \right.\right\} </math>}}<br />
<br />
<math>L</math> が多項式時間で決定可能であり、かつ与えられた <math> \langle A,k \rangle </math> について <math> \langle A,k \rangle \in CM</math> であることと全ての入力 <math>x</math> について <math> \langle A,k,B,x \rangle \in L </math> となる回路 <math>B</math> が存在することは同値であることから、<math> CM \in \Sigma_2^P (= \exists^{\rm P} \forall^{\rm P} {\rm P}) </math> が成り立つ。<br />
</li><li><br />
<math>\Sigma_k^{\rm P}</math> の完全問題として ''k''回の量化子交替のある「限量記号付きブール式問題」（'''QBF<sub>k</sub>''' または '''QSAT<sub>k</sub>''' と略記される）がある。これは[[充足可能性問題]]を <math>\Sigma_k^{\rm P}</math> 向けにしたものである。この問題では、与えられるブール論理式 ''f'' の変数は ''k'' 個の集合 ''X<sub>1</sub>'', ..., ''X<sub>k</sub>'' に分けられる。ここで次が真かどうかを決定しなくてはならない。<br />
<br />
{{Indent|<math> \exists X_1 \forall X_2 \exists X_3 \ldots f</math>}}<br />
<br />
すなわち、''X<sub>1</sub>'' に ''f'' を満足する値の組合せがあり、かつ ''X<sub>2</sub>'' の値の全ての組合せが ''f'' を満足し、かつ ''X<sub>3</sub>'' に ''f'' を満足する値の組合せがあり、… という組合せが存在するかどうか、という問題である。この順序の問題は <math>\Sigma_k^{\rm P}</math> について完全である。全称記号が最初にあって、次が存在記号という順序になっている問題は <math>\Pi_k^{\rm P}</math> について完全である。<br />
</li><br />
</ul><br />
<br />
== 参考文献 ==<br />
* A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. ''In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory'', pp. 125&ndash;129, 1972. 多項式階層を提唱した論文。<br />
* L. J. Stockmeyer. [http://dx.doi.org/10.1016/0304-3975(76)90061-X The polynomial-time hierarchy]. ''Theoretical Computer Science'', vol.3, pp.1&ndash;22, 1976.<br />
* C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. ''Polynomial hierarchy'', pp. 409&ndash;438.<br />
* {{cite book|author = Michael R. Garey and David S. Johnson | date = 1979年 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} Section 7.2: The Polynomial Hierarchy, pp.161&ndash;167.<br />
<br />
{{複雑性クラス}}<br />
<br />
{{DEFAULTSORT:たこうしきかいそう}}<br />
[[Category:計算複雑性理論]]<br />
[[Category:数学に関する記事]]<br />
[[Category:ヒエラルキー]]</div>175.177.5.26 Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46