翻訳と辞書 Words near each other ・ 複雑ネットワーク ・ 複雑化 ・ 複雑型細胞 ・ 複雑多岐 ・ 複雑多様 ・ 複雑奇怪 ・ 複雑微妙 ・ 複雑性 ・ 複雑性PTSD ・ 複雑性の科学 ・ 複雑性クラス ・ 複雑性尿路感染症 ・ 複雑性悲嘆 ・ 複雑性歯牙腫 ・ 複雑性理論 ・ 複雑怪奇 ・ 複雑歯牙腫 ・ 複雑窩洞 ・ 複雑系 ・ 複雑系の数理 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 複雑性クラス ： ウィキペディア日本語版 複雑性クラス[ふくざつせいくらす] 複雑性クラス（ふくざつせいクラス、）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 :抽象機械 M によりO(f(''n''))の計算資源 R を使って解く事が出来る問題の集合（''n''は入力長） 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えばFP）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。 ==複雑性クラス間の関係== 以下の表はいくつかの問題（または文法、言語）のクラスを計算複雑性理論の中で捉えて図示したものである。クラス X が Y の真部分集合である場合、X を Y の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。 決定問題 image:solidLine.png image:solidLine.png Type 0 （帰納的可算） 決定不能 image:solidLine.png 決定可能 image:solidLine.png EXPSPACE image:dottedLine.png EXPTIME image:dottedLine.png PSPACE image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png Type 1 （文脈依存） image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png PSPACE完全 image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:solidLine.png image:solidLine.png Co-NP image:dottedLine.png image:dottedLine.png NP image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:solidLine.png image:solidLine.png image:dottedLine.png BPP BQP NP完全 image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:solidLine.png image:solidLine.png P image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:solidLine.png NC P完全 image:solidLine.png image:solidLine.png Type 2 （文脈自由） image:solidLine.png Type 3 （正規） 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「複雑性クラス」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.