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=101.111.248.146miniwiki - 利用者の投稿記録 [ja]2024-06-29T05:21:59Z利用者の投稿記録MediaWiki 1.31.0記述計算量2014-12-22T12:18:57Z<p>101.111.248.146: /* 概要 */</p>
<hr />
<div>'''記述計算量'''（きじゅつけいさんりょう、{{lang-en-short|Descriptive complexity}}）は、[[有限モデル理論]]の一種であり、[[計算複雑性理論]]と[[数理論理学]]の一分野である。[[複雑性クラス]]を言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、[[PH (計算複雑性理論)|'''PH''']]は[[二階述語論理]]の論理式で表現される言語のクラスと正確に対応している。このような[[複雑性]]と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の[[抽象機械]]に結びつくものではないことを示すことができる。<br />
<br />
== 概要 ==<br />
特に、それぞれの論理体系は、その中で表現可能なクエリの集合を生み出す。クエリは計算複雑性理論における計算問題と対応している。<br />
<br />
記述計算量の最初の成果として、1974年に[[ロナルド・フェイギン]]が示した Fagin の定理がある<ref name="fagin1974"> [http://www.almaden.ibm.com/cs/people/fagin/ R. Fagin]. [http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf Generalized First-Order Spectra and Polynomial-Time Recognizable Sets]. ''Complexity of Computation'', ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27-41. 1974.</ref>。これは、'''[[NP]]'''が存在量化二階述語論理の論理式で表現可能な言語の集合と正確に対応していることを示した。存在量化二階述語論理とは、関係・関数・部分集合について[[全称記号|全称量化]]を行わない二階述語論理である。他の多くのクラスについても、主に Neil Immerman によって同様の特徴付けがなされた。以下に主なものを列挙する。<br />
* [[一階述語論理]]はクラス '''FO'''（あるいは '''AC<sup>0</sup>'''）を定義し、その言語は定数深さの多項式サイズ回路で認識される。これは並行ランダムアクセス機械（CRAM、CRCW型の[[並列ランダムアクセス機械|PRAM]]にほぼ相当するモデル）で[[定数時間]]で認識される言語と等価である。<br />
* 一階述語論理に可換な[[推移閉包]]演算子を追加したものは、'''[[SL (計算複雑性理論)|SL]]''' に相当する。これは対数領域で解ける問題のクラス [[L (計算複雑性理論)|'''L''']] と等しい。<br />
* 一階述語論理に推移閉包演算子を追加したものは、[[NL (計算複雑性理論)|'''NL''']] に相当する。<br />
* 線形順序が存在する場合、[[最小不動点]]演算子を持つ一階述語論理が [[P (計算複雑性理論)|'''P''']] に相当する。<br />
* 存在量化二階述語論理は '''[[NP]]''' に相当する（上述の通り）。<br />
* 二階存在量化をのぞいた全称二階述語論理は co-'''NP''' に相当する。<br />
* 二階述語論理は [[PH (計算複雑性理論)|'''PH''']] に相当する。<br />
* 推移閉包演算子を持つ二階述語論理は '''[[PSPACE]]''' に相当する。<br />
* 最小不動点演算子を持つ二階述語論理は '''[[EXPTIME]]''' に相当する。<br />
<br />
== 参考文献 ==<br />
* [http://www.almaden.ibm.com/cs/people/fagin/ R. Fagin]. [http://www.almaden.ibm.com/cs/people/fagin/tcs93.pdf Finite model theory-a personal perspective]. Theoretical Computer Science 116, 1993, pp. 3-31. <br />
* Neil Immerman. [http://www.cs.umass.edu/~immerman/pub/capture.pdf Languages Which Capture Complexity Classes]. ''15th ACM STOC Symposium'', pp.347-354. 1983.<br />
* [http://www.cs.umass.edu/~immerman/descriptive_complexity.html Neil Immerman's descriptive complexity page]、図解付き<br />
<br />
== 脚注 ==<br />
{{Reflist}}<br />
<br />
{{DEFAULTSORT:きしゆつけいさんりよう}}<br />
<br />
[[Category:数理論理学]]<br />
[[Category:計算複雑性理論]]<br />
[[Category:数学に関する記事]]</div>101.111.248.146 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