查看“︁NEXPTIME”︁的源代码

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

以[[NTIME]]作定義

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

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

如果[[P/NP問題|'''P''' = '''NP''']]，那麼'''NEXPTIME''' = '''EXPTIME'''；更精確的說，'''[[E (複雜度)|E]]''' ≠ '''[[NE (複雜度)|NE]]'''，若且唯若存在一個[[稀疏語言]]，在'''NP'''並且不在'''P'''裡面。<ref>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. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library] {{Webarchive|url=https://archive.today/20120712205722/http://portal.acm.org/citation.cfm?id=808769 |date=2012-07-12 }}</ref>

<!--== Alternative characterizations ==

'''NEXPTIME''' often arises in the context of [[interactive proof system]]s, where there are two major characterizations of it. The first is the '''MIP''' proof system, where we have two all-powerful provers which communicate with a randomized polynomial-time verifier (but not with each other). If the string is in the language, they must be able to convince the verifier of this with high probability. If the string is not in the language, they must not be able to collaboratively trick the verifier into accepting the string except with low probability. The fact that '''MIP''' proof systems can solve every problem in '''NEXPTIME''' is quite impressive when we consider that when only one prover is present, we can only recognize all of '''PSPACE'''; the verifier's ability to "cross-examine" the two provers gives it great power. See [[interactive proof system#MIP]] for more details.

Another interactive proof system characterizing '''NEXPTIME''' is a certain class of [[probabilistically checkable proof]]s. Recall that '''NP''' can be seen as the class of problems where an all-powerful prover gives a purported proof that a string is in the language, and a deterministic polynomial-time machine verifies that it is a valid proof. We make two changes to this setup:

* Add randomness, the ability to flip coins, to the verifier machine.
* Instead of simply giving the purported proof to the verifier on a tape, give it random access to the proof. The verifier can specify an index into the proof string and receive the corresponding bit. Since the verifier can write an index of polynomial length, it can potentially index into an exponentially long proof string.

These two extensions together greatly extend the proof system's power, enabling it to recognize all languages in '''NEXPTIME'''. The class is called '''PCP'''(poly, poly). See [[probabilistically checkable proof]]s for more details.-->

==相關條目==
*[[遊戲複雜度]]

==參考資料==
<references/>

* {{CZoo|NEXP|N#nexp}}, {{CZoo|coNEXP|C#conexp}}

{{複雜度類}}

{{DEFAULTSORT:Nexptime}}
[[Category:複雜度類]]