NEXPTIME
Encyclopedia
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 O
(2p(n)) for some polynomial p(n), and unlimited space.
In terms of NTIME
,
An important set of NEXPTIME-complete problems relates to succinct 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 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"). As one simple example, finding a Hamiltonian path
for a graph thus encoded is NEXPTIME-complete.
If P = NP, then NEXPTIME = EXPTIME (padding argument
); more precisely, E
≠ NE
if and only if there exist sparse language
s in NP that are not in P.
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 proofs. 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:
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 proofs for more details.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
NEXPTIME (sometimes called NEXP) is the set of decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that can be solved by a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
using time O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(2p(n)) for some polynomial p(n), and unlimited space.
In terms of NTIME
NTIME
In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space....
,
An important set of NEXPTIME-complete problems relates to succinct 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 an adjacency matrix, is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, 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"). As one simple example, finding a Hamiltonian path
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
for a graph thus encoded is NEXPTIME-complete.
If P = NP, then NEXPTIME = EXPTIME (padding argument
Padding argument
In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal.- Example :If P is equal to NP then EXP is equal to NEXP...
); more precisely, E
E (complexity)
In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2O and is therefore equal to the complexity class DTIME....
≠ NE
NE (complexity)
In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time O for some k....
if and only if there exist sparse language
Sparse language
In computational complexity theory, a sparse language is a formal language such that the number of strings of length n in the language is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes...
s in NP that are not in P.
Alternative characterizations
NEXPTIME often arises in the context of interactive proof systemInteractive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
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 proofs. 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 proofs for more details.