Ladner's theorem
Encyclopedia
In computational complexity
, problems that are in the complexity class
NP
but are neither in the class P
nor NP-complete
are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete
. Since the other direction is trivial, we can say that P = NP if and only if NPI is empty.
Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, however this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem
, factoring
, and computing the discrete logarithm
.
Another problem in NP that is not known to be in P or NP-complete is the minimum circuit size problem (MCSP)
. Unlike the above problems, MCSP is believed to be in NP-complete. However, proving as much via a many-one reduction
will imply circuit lower bounds for E
(unless NP is contained in SUBEXP, which is a violation of the exponential time hypothesis
). Therefore, proving that MCSP is in NP-complete is considered outside of current techniques.
A large list of natural problems with potentially intermediate complexity has been created by users of Theoretical Computer Science Stack Exchange.
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
, problems that are in 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:...
NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
but are neither in the class P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
nor 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...
are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor 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...
. Since the other direction is trivial, we can say that P = NP if and only if NPI is empty.
Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, however this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
, factoring
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
, and computing the discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
.
Another problem in NP that is not known to be in P or NP-complete is the minimum circuit size problem (MCSP)
Circuit minimization
In Boolean algebra, circuit minimization is the problem of obtaining the smallest logic circuit that represents a given Boolean function or truth table...
. Unlike the above problems, MCSP is believed to be in NP-complete. However, proving as much via a many-one reduction
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
will imply circuit lower bounds for 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....
(unless NP is contained in SUBEXP, which is a violation of the exponential time hypothesis
Exponential time hypothesis
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption formalized by stating that 3-SAT cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP...
). Therefore, proving that MCSP is in NP-complete is considered outside of current techniques.
A large list of natural problems with potentially intermediate complexity has been created by users of Theoretical Computer Science Stack Exchange.
External links
- Basic structure, Turing reducibility and NP-hardness
- Lance Fortnow, Foundations of Complexity, Lesson 16: Ladner’s Theorem. Accessed 17/09/2009
- NP completeness