imported>HTinC23：WPCleaner v2.05 - 內鏈消歧義 - 集合

2023-02-28T20:42:20Z

WPCleaner v2.05 - 內鏈消歧義 - 集合

新页面

在[[計算複雜度理論]]內，'''EXPSPACE'''是一個包含可以在[[大O符號|O]](2<sup>''p''(''n'')</sup>)空間內解決的[[決定性問題]]的[[集合 (数学)|集合]]，這裡的''p(n)''是某個n的多項式。（有些作者認為''p''(''n''）應該限制為[[線性函數]]，但是多數的人把這這樣的複雜度類稱作'''ESPACE'''。)如果我們使用非決定性圖靈機，我們會得到複雜度類'''NEXPSPACE'''。根據[[薩維奇定理]]，這個複雜度類等同'''EXPSPACE'''。

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

:<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k}) = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})</math>

我們說一個問題是'''EXPSPACE-完全'''，如果這問題本身在'''EXPSPACE'''內，而且存在多項式多對一歸約，令所有在'''EXPSPACE'''內的題目都可以歸約成這個題目。換句話說，存在一個多項式時間的[[演算法]]可以將一個狀況換成其他題目的另一個狀況，並且答案一樣。'''EXPSPACE-完全'''的題目也可以想做是'''EXPSPACE'''裡面最難的題目。

'''EXPSPACE'''是'''[[PSPACE]]'''，'''[[NP (複雜度)|NP]]'''，和'''[[P (複雜度)|P]]'''的嚴格母集（前者包含且不等於後者）。並且也被相信是'''[[EXPTIME]]'''的嚴格母集。

一個'''EXPSPACE-完全'''的例子是分辨兩個[[正規表式]]是否是一樣的語言這個問題。這裡的表示限制使用四種操作子：聯集，[[串街]]，[[克萊尼星號]]（可以是零個或多個重複的表示式），和平方（兩份表示式）。<ref>Meyer, A.R. and [[Larry Stockmeyer|L. Stockmeyer]]. [http://people.csail.mit.edu/meyer/rsq.pdf The equivalence problem for regular expressions with squaring requires exponential space] {{Wayback|url=http://people.csail.mit.edu/meyer/rsq.pdf |date=20110519063201 }}. ''13th IEEE Symposium on Switching and Automata Theory'', Oct 1972, pp.125–129.</ref>

如果我們排除星號，則這個問題變成'''[[NEXPTIME]]-完全'''，這個複雜度類有點類似'''EXPTIME-完全'''，不過使用的機器是[[非決定性圖靈機]]而非一般的圖靈機。

L. Berman在1980年證明了，證明或反證任何有關[[實數]]並且牽涉[[加法]]和比較大小（但不牽涉[[乘法]]）的[[一階邏輯|一階]]陳述，這個問題在'''EXPSPACE'''內。

==相關頁面==
*[[遊戲複雜度]]

== 參考資料 ==

<references />
* L. Berman ''The complexity of logical theories'', Theoretical Computer Science 11:71-78, 1980.
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | isbn = 0-534-94728-X}} Section 9.1.1: Exponential space completeness, pp.313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.

{{複雜度類}}

[[Category:複雜度類]]

EXPSPACE - 版本历史

imported>HTinC23：​WPCleaner v2.05 - 內鏈消歧義 - 集合

imported>HTinC23：WPCleaner v2.05 - 內鏈消歧義 - 集合