檢視 EXPSPACE 的原始碼

佇咧算複雜度理論內，'''EXPSPACE'''是一个包括會當佇 O ( 二 p ( _ n _ ) ) 空間內解決的決定性問題的集合，遮的 _ p ( n ) _ 是某一个 n 的多項式。（有的作者認為講 _ p _ ( _ n _）應該限制做線性函數，但是多數的人共這款的複雜度類號做'''ESPACE'''。) 咱若使用非決定性圖靈機，咱會得著複雜度類'''NEXPSPACE'''。根據薩維奇定理，這个複雜度類等同'''EXPSPACE'''。

以'''DSPACE'''和'''NSPACE'''表示：


: $ { \ mbox { EXPSPACE } }=\ bigcup _ { k \ in \ mathbb { N } } { \ mbox { DSPACE } } ( 二 ^ { n ^ { k } } )=\ bigcup _ { k \ in \ mathbb { N } } { \ mbox { NSPACE } } ( 二 ^ { n ^ { k } } ) $

咱講一个問題是'''EXPSPACE-完全'''，抑若這个問題本身佇咧'''EXPSPACE'''內，而且閣存在多項式濟嘿歸約，令所有咧'''EXPSPACE'''內的題目攏會當歸約做這个題目。嘛會使講，佇一个多項式時間的演算法會當共一个狀況換做其他題目的另外一个狀況，並且答案仝款。'''EXPSPACE-完全'''的題目嘛會當想欲做是'''EXPSPACE'''內底上難的題目。

'''EXPSPACE'''是'''PSPACE'''，'''NP'''，和'''P'''的嚴格母集（這个頭家包括而且無等於後者）。 並且嘛予人相信講是'''EXPTIME'''的嚴格母集。

一个'''EXPSPACE-完全'''的例是分辨兩个正規表式敢是仝款的語言這个問題。遮的表示限制使用四種的操作子：聯集，貫街仔，克萊尼星號（會當是零个抑是濟重複的表示式）， 和平方（兩份表示式）。

若阮排除天星號，著這个問題變做'''NEXPTIME-完全'''，這个複雜度類似有淡薄仔類似'''EXPTIME-完全'''，毋過使用的機器是非決定性圖靈機非一般的圖靈機。

L . Berman 佇一九八Ｏ年證明了，證明抑是反證任何有關實數並且牽涉加法佮較大細（但無牽涉乘法）的一階陳述，這个問題佇咧'''EXPSPACE'''內。

==相關頁面==

* 遊戲複雜度

==參考資料==

* L . Berman _ The complexity of logical theories _ , Theoretical Computer Science 十一 : 七十一孵七十八 , 一千九百八十 .
* Michael Sipser . Introduction to the Theory of Computation . PWS Publishing . 一千九百九十七 . ISBN  空白五百三十四鋪九九四千七百二十八-X .   Section 九陽一 . 一 : Exponential space completeness , pp . 三百十三–三百一十七 . Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete .

[[分類: 待校正]]