Incomputational complexity theory, thecomplexity classNEXPTIME (sometimes calledNEXP) is the set ofdecision problems that can be solved by anon-deterministic Turing machine using time${\displaystyle 2^{n^{O(1)}}}$.

In terms ofNTIME,

${\displaystyle \mathsf{N}\mathsf{E}\mathsf{X}\mathsf{P}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}=\bigcup _{k\in \mathbb{N}}\mathsf{N}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(2^{n^k})}$

Alternatively,NEXPTIME can be defined using deterministic Turing machines as verifiers. AlanguageL is inNEXPTIME if and only if there exist polynomialsp andq, and a deterministic Turing machineM, such that

• For allx andy, the machineM runs in time${\displaystyle 2^{p(|x|)}}$ on input⁠${\displaystyle (x,y)}$⁠
• For allx inL, there exists a stringy of length${\displaystyle 2^{q(|x|)}}$ such that⁠${\displaystyle M(x,y)=1}$⁠
• For allx not inL and all stringsy of length${\displaystyle 2^{q(|x|)}}$,⁠${\displaystyle M(x,y)=0}$⁠

We know

P ⊆NP ⊆EXPTIME ⊆ NEXPTIME

and also, by thetime hierarchy theorem, that

NP ⊊ NEXPTIME

IfP = NP, thenNEXPTIME = EXPTIME (padding argument); more precisely,E ≠NE if and only if there existsparse languages inNP that are not inP.^[1]

Indescriptive complexity, the sets of natural numbers that can be recognized in NEXPTIME are exactly those that form thespectrum of a sentence, the set of sizes offinite models of some logical sentence.^[2]

NEXPTIME often arises in the context ofinteractive proof systems, where there are two major characterizations of it. The first is theMIP 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 thatMIP proof systems can solve every problem inNEXPTIME is quite impressive when we consider that when only one prover is present, we can only recognize all ofPSPACE; the verifier's ability to "cross-examine" the two provers gives it great power. Seeinteractive proof system#MIP for more details.

Another interactive proof system characterizingNEXPTIME is a certain class ofprobabilistically checkable proofs. Recall thatNP 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 inNEXPTIME. The class is calledPCP(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). Seeprobabilistically checkable proofs for more details.

A decision problem is NEXPTIME-complete if it is in NEXPTIME, and every problem in NEXPTIME has apolynomial-time many-one reduction to it. In other words, there is a polynomial-timealgorithm that transforms instances of one to instances of the other with the same answer. Problems that are NEXPTIME-complete might be thought of as the hardest problems in NEXPTIME. We know that NEXPTIME-complete problems are not in NP; it has been proven that these problems cannot be verified inpolynomial time, by thetime hierarchy theorem.

An important set ofNEXPTIME-complete problems relates tosuccinct circuits. 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 anadjacency matrix, isNP-complete, then solving the same problem on a succinct circuit representation isNEXPTIME-complete, because the input is exponentially smaller (under some mild condition that the NP-completeness reduction is achieved by a "projection").^[3][4] As one simple example, finding aHamiltonian path for a graph thus encoded isNEXPTIME-complete.

The satisfiability problem of first-order logic with two variables is NEXPTIME-complete.^[5] The satisfiability problem of first-order logic with counting and with two variables is NEXPTIME-complete.^[6]

Deciding whether a formula in Dependency quantified binary formulas (DQBF, which is an imperfect information version ofQBF) is true is NEXPTIME-complete.^[7] The imperfect information with teams ofconstraint logic is NEXPTIME-complete too.^[8]

• Game complexity
• NP
• EXPTIME

• Complexity Zoo:NEXP,Complexity Zoo:coNEXP
• Arora, Sanjeev; Barak, Boaz (2009),Computational Complexity: A Modern Approach,Cambridge, p. 57,ISBN 978-0-521-42426-4

• Complexity classes

• Articles with short description
• Short description is different from Wikidata