In terms of NTIME, Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers.
A language L is in NEXPTIME if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that We know and also, by the time hierarchy theorem, that If P = NP, then NEXPTIME = EXPTIME (padding argument); more precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.[1] In descriptive complexity, the sets of natural numbers that can be recognized in NEXPTIME are exactly those that form the spectrum of a sentence, the set of sizes of finite models of some logical sentence.
We make two changes to this setup: These two extensions together greatly extend the proof system's power, enabling it to recognize all languages in NEXPTIME.
What more, in this characterization the verifier may be limited to read only a constant number of bits, i.e. NEXPTIME = PCP(poly, 1).
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").