computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

, problems that are in the

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms ...

NP but are neither in the class P nor

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. 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 it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty. Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property: Schaefer's dichotomy theorem provides conditions under which classes of constrained Boolean satisfiability problems cannot be in NPI. Some problems that are considered good candidates for being NP-intermediate are the

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational comp ...

, factoring, and computing the

discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log' ...

List of problems that might be NP-intermediate

Algebra and number theory

* Factoring integers * Discrete Log Problem and others related to cryptographic assumptions * Isomorphism problems: Group isomorphism problem,

Group automorphism In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two grou ...

, Ring isomorphism, Ring automorphism * Linear divisibility: given integers

x

and

y

, does

y

have a divisor congruent to 1 modulo

x

Boolean logic

* IMSAT, the

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies ...

for "intersecting monotone CNF": conjunctive normal form, with each clause containing only positive or only negative terms, and each positive clause having a variable in common with each negative clause * Minimum Circuit Size Problem * Monotone self-duality: given a CNF formula for a Boolean function, is the function invariant under a transformation that negates all of its variables and then negates the output value?

Computational geometry and computational topology

* Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon * The turnpike problem of reconstructing points on line from their distance multiset * The cutting stock problem with a constant number of object lengths * Knot triviality * Finding a simple closed quasigeodesic on a convex polyhedron

Game theory

* Determining winner in parity games, in which graph vertices are labeled by which player chooses the next step, and the winner is determined by the parity of the highest-priority vertex reached * Determining the winner for stochastic graph games, in which graph vertices are labeled by which player chooses the next step, or whether it is chosen randomly, and the winner is determined by reaching a designated sink vertex.

Graph algorithms

Graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational comp ...

* Planar minimum bisection * Deciding whether a graph admits a graceful labeling * Recognizing leaf powers and -leaf powers * Recognizing graphs of bounded clique-width * Finding a simultaneous embedding with fixed edges

Miscellaneous

* Problems in TFNP * Pigeonhole subset sum: given

n

positive integers whose sum is less than

2^n-1

, find two distinct subsets with the same sum * Finding the Vapnik–Chervonenkis dimension of a given family of sets

References

External links

*
Basic structure, Turing reducibility and NP-hardness
* {{DEFAULTSORT:Np-Intermediate Complexity classes