|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 完 ： [かん] 【名詞】 1. The End (book, film, etc.) 2. Finis ・ 全 ： [ぜん] 1. (n,pref) all 2. whole 3. entire 4. complete 5. overall 6. pan
PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。 == 概要 == PSPACE とはチューリングマシンによって多項式領域で解ける問題、すなわち使用するテープの長さが問題のサイズの多項式で収まる決定問題のクラスのことである（処理にかかる時間は問わない）。 多項式時間で解ける問題は当然ながらテープの使用回数も問題のサイズの多項式に比例するので P ⊆ PSPACE であることは自明である。またNP ⊆ PSPACE であることも証明されている。 このクラスに NP と同様の概念を当てはめたクラス、すなわち答えが与えられたときその検算が PSPACE になる NPSPACE というクラスを考えることもできるが、1970年 ウォルター・サヴィッチ（Walter Savitch）のサヴィッチの定理により PSPACE = NPSPACE ということが証明された。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PSPACE」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 PSPACE 」があります。 スポンサード リンク
|