NEXPTIME

在計算複雜度理論內，複雜度類NEXPTIME（有時叫做NEXP）是一個決定性問題的集合，包含可以使用非確定型圖靈機，使用O(2^p(n))（這裏的p(n)是某個多項式）的時間可以解決的問題。另外這裏不限制空間的使用。

以NTIME作定義

{\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(2^{n^{k}})

一個很重要的NEXPTIME-完全問題集合與簡潔電路（succinct circuit）有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連接矩陣，去解決時是個NP-完全問題，那麼使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。^[1]舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。

如果P = NP，那麼NEXPTIME = EXPTIME；更精確的說，E ≠ NE，若且唯若存在一個稀疏語言，在NP並且不在P裏面。^[2]

參考資料

^ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library Archive.is的存檔，存檔日期2012-07-12

Complexity Zoo: NEXP, Complexity Zoo: coNEXP

[1] C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.

[2] Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library Archive.is的存檔，存檔日期2012-07-12

[1]

[2]

NEXPTIME

相關條目

參考資料