翻訳と辞書
Words near each other
・ 複雑ネットワーク
・ 複雑化
・ 複雑型細胞
・ 複雑多岐
・ 複雑多様
・ 複雑奇怪
・ 複雑微妙
・ 複雑性
・ 複雑性PTSD
・ 複雑性の科学
複雑性クラス
・ 複雑性尿路感染症
・ 複雑性悲嘆
・ 複雑性歯牙腫
・ 複雑性理論
・ 複雑怪奇
・ 複雑歯牙腫
・ 複雑窩洞
・ 複雑系
・ 複雑系の数理


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

複雑性クラス : ウィキペディア日本語版
複雑性クラス[ふくざつせいくらす]
複雑性クラス(ふくざつせいクラス、)は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。
:抽象機械 M によりO(f(''n''))の計算資源 R を使って解く事が出来る問題の集合(''n''は入力長)
例えば、クラスNP非決定性チューリングマシン多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEチューリングマシン多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である(例えばFP)。
数理論理学では表現の必要に応じて多数の複雑性クラスが定義される(記述計算量)。
ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。
==複雑性クラス間の関係==
以下の表はいくつかの問題(または文法、言語)のクラスを計算複雑性理論の中で捉えて図示したものである。クラス XY真部分集合である場合、XY の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。








































































































































決定問題
image:solidLine.pngimage:solidLine.png
Type 0 (帰納的可算)
決定不能
image:solidLine.png
決定可能
image:solidLine.png
EXPSPACE
image:dottedLine.png
EXPTIME
image:dottedLine.png
PSPACE
image:solidLine.pngimage:solidLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.png
Type 1 (文脈依存)
image:solidLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.png
PSPACE完全
image:solidLine.pngimage:solidLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.png
image:solidLine.pngimage:solidLine.png
Co-NP
image:dottedLine.pngimage:dottedLine.png
NP
image:solidLine.pngimage:solidLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.png
image:solidLine.pngimage:solidLine.pngimage:dottedLine.png
BPP
BQP
NP完全
image:solidLine.pngimage:solidLine.pngimage:dottedLine.pngimage:dottedLine.pngimage:dottedLine.png
image:solidLine.pngimage:solidLine.png
P
image:solidLine.pngimage:solidLine.pngimage:dottedLine.pngimage:dottedLine.png
image:solidLine.png
NC
P完全
image:solidLine.pngimage:solidLine.png
Type 2 (文脈自由)
image:solidLine.png
Type 3 (正規)


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「複雑性クラス」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.