複雑性クラス間の関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/28 02:38 UTC 版)
「複雑性クラス」の記事における「複雑性クラス間の関係」の解説
以下の表はいくつかの問題（または文法、言語）のクラスを計算複雑性理論の中で捉えて図示したものである。クラス X が Y の真部分集合である場合、X を Y の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。 決定問題 Type 0 （帰納的可算） 決定不能 決定可能 EXPSPACE EXPTIME PSPACE Type 1 （文脈依存） PSPACE完全 Co-NP NP BPP BQP NP完全 P NC P完全 Type 2 （文脈自由） Type 3 （正規）
※この「複雑性クラス間の関係」の解説は、「複雑性クラス」の解説の一部です。
「複雑性クラス間の関係」を含む「複雑性クラス」の記事については、「複雑性クラス」の概要を参照ください。
ウィキペディア小見出し辞書の「複雑性クラス間の関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 複雑性クラス間の関係のページへのリンク
