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