「計算複雑性理論」の版間の差分
削除された内容 追加された内容
m編集の要約なし |
|||
57行目:
多くの複雑性クラスは、それを表現するのに必要となる[[形式体系|論理体系]]によって特徴付けられる。これは、[[記述計算量]]の概念と関係がある。
各クラスに対し、そのクラスの'''完全問題'''を考えることがある。クラス''C''の完全問題とは''C''に属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。
;
:クラス''C''に対して、問題''P''が''C'''''困難'''であるとは、''C''に属する任意の問題を''P''に帰着（多くの場合[[多項式時間変換|多項式時間帰着]]を考えるが、そうでない場合もある<!--NP完全問題の定義としてlog space帰着を採用する場合もある-->）できるということである。すなわち''P''は''C''に属するいかなる問題よりも、同等かそれ以上に難しいということである。ただし、''C'''''完全'''と異なり、''P''自身は''C''に属するとは限らない。
;
:クラス''C''に対して、問題''P''が''C'''''完全'''であるとは、''P''が''C''に属しかつ''C''困難ということである。すなわち''P''は''C''に属する問題の中で、本質的に最も難しい問題であるということである。
71 ⟶ 69行目:
* [[NC (計算複雑性理論)|NC]]
* [[P (計算複雑性理論)|P]]
* [[NP]]
* [[co-NP]]
* [[PSPACE]]
94 ⟶ 92行目:
==イントラクタブル==
{{see also|組合せ爆発}}
理論上計算可能な問題であっても、実際に解くことができない問題を'''イントラクタブル'''
[[指数関数時間]]の解法がなぜ実際には使えないかを考えるため、2<
== 主な研究者 ==
* [[マヌエル・ブラム]]: [[ブラムの公理]]に基づいた公理的複雑性理論を構築した
* [[スティーブン・クック]]
* [[ユリス・ハルトマニス]]
107 ⟶ 105行目:
* [[アンドリュー・チーチー・ヤオ]]
* [[レスリー・ヴァリアント]]
*
== 脚注 ==
| |||