View source for Quantum logic

In [[computational complexity theory]], the [[complexity class]] '''NEXPTIME''' (sometimes called '''NEXP''') is the set of [[decision problem]]s that can be solved by a [[non-deterministic Turing machine]] using time [[Big O notation|O]](2<sup>''p''(n)</sup>) for some [[polynomial]] ''p''(n), and unlimited space.

In terms of [[NTIME]],

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

An important set of '''NEXPTIME'''-complete problems relates to [[succinct circuit]]s. Succinct circuits are simple machines used to describe graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. If solving a problem on a graph in a natural representation, such as an [[adjacency matrix]], is [[NP-complete]], then solving the same problem on a succinct circuit representation is '''NEXPTIME'''-complete, because the input is exponentially smaller (under some mild condition that the NP-completeness reduction is achieved by a "projection").<ref>[[Christos Papadimitriou|C. Papadimitriou]] & [[Mihalis Yannakakis|M. Yannakakis]], ''A note on succinct representations of graphs'',  Information and control, vol 71 num 3, décember 1986, pp. 181—185, {{doi|10.1016/S0019-9958(86)80009-2}}</ref><ref>C. Papadimitriou. ''Computational Complexity'' Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.</ref> As one simple example, finding a [[Hamiltonian path]] for a graph thus encoded is '''NEXPTIME'''-complete.

If [[P = NP problem|'''P''' = '''NP''']], then '''NEXPTIME''' = '''EXPTIME''' ([[padding argument]]); more precisely, '''[[E (complexity)|E]]''' ≠ '''[[NE (complexity)|NE]]''' if and only if there exist [[sparse language]]s in '''NP''' that are not in '''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&ndash;181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</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). What more, in this characterization the verifier may be limited to read only a constant number of bits, i.e. '''NEXPTIME''' = '''PCP'''(poly, 1). See [[probabilistically checkable proof]]s for more details.

==See also==
*[[Game complexity]]

==References==
<references/>

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

{{ComplexityClasses}}

{{DEFAULTSORT:Nexptime}}
[[Category:Complexity classes]]