In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic...

EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem and the space hierarchy theorem, it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE...

classes relate to each other in the following way: L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆EXPSPACE (where ⊆ denotes the subset relation). However, many relationships...

NE, unlike the similar class NEXPTIME, is not closed under polynomial-time many-one reductions. NE is contained by NEXPTIME. E (complexity) Complexity Zoo:...

fragment where the only variable names are x , y {\displaystyle x,y} is NEXPTIME-complete (Theorem 3.18). With x , y , z {\displaystyle x,y,z} , it is RE-complete...

even EXPTIME = MA. If NEXPTIME ⊆ P/poly then NEXPTIME = EXPTIME, even NEXPTIME = MA. Conversely, NEXPTIME = MA implies NEXPTIME ⊆ P/poly If EXPNP ⊆ P/poly...

EXPSPACE O(2poly(n)) Time Non-Deterministic NTIME(f(n)) O(f(n)) NP O(poly(n)) NEXPTIME O(2poly(n)) Deterministic DTIME(f(n)) O(f(n)) P O(poly(n)) EXPTIME O(2poly(n))...

respectively they are N P ⊊ N E X P T I M E {\displaystyle {\mathsf {NP\subsetneq NEXPTIME}}} and N P ⊊ E X P S P A C E {\displaystyle {\mathsf {NP\subsetneq EXPSPACE}}}...

show that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. NEXPTIME contains PSPACE...

grounding or instantiation. The satisfiability problem for this class is NEXPTIME-complete. Efficient algorithms for deciding satisfiability of EPR have...

linear exponent NEXP Same as NEXPTIME NEXPSPACE Solvable by a non-deterministic machine with exponential space NEXPTIME Solvable by a non-deterministic...

then NEXPTIME is not a subset of P/poly. Williams shows that, if algorithm A {\displaystyle A} exists, and a family of circuits simulating NEXPTIME in P/poly...

Selman, it is equivalent to the problem of whether NEXPTIME = co-NEXPTIME; that is, whether NEXPTIME is closed under complementation. Spectrum of a theory...

{\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}} . It is open whether NEXPTIME has nonuniform TC0 circuits. Proofs of circuit lower bounds are strongly...

genuine hierarchies: in other words P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... and NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ .... For example, P ⊊ E X P T I M E {\displaystyle {\mathsf...

Complexity O MC(O) MF(O) ∪,∩,−,+,× NEXPTIME-hard Decidable with an oracle for the halting problem PSPACE-hard ∪,∩,+,× NEXPTIME-complete NP-complete ∪,+,× PSPACE-complete...

{DTIME}}\left(2^{2^{n^{k}}}\right).} We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY. 2-EXPTIME can also be reformulated...

{\displaystyle _{\mathbb {Z} }} (O) ∪,∩,−,+,× NEXPTIME-hard PSPACE-hard ∪,∩,+,× NEXPTIME-complete NP-complete ∪,+,× NEXPTIME-complete NP-complete ∩,+,× P-hard, in...

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...

Computer Science characterizing complexity classes such as PSPACE and NEXPTIME in terms of interactive proof systems; this work became part of his 1991...

complexity. For instance, he shows that the Bernays–Schönfinkel class is NEXPTIME-complete, and more specifically that its nondeterministic time complexity...

(Aug 1993). Systems of Set Constraints with Negative Constraints are NEXPTIME-Complete (Technical report). Computer Science Department, Cornell University...

proof of Toda's theorem. Williams (2011) proves that ACC0 does not contain NEXPTIME. The proof uses many results in complexity theory, including the time hierarchy...

so helpful that Babai, Fortnow, and Lund were able to show that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential...