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 (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

NP but are neither in the class P nor

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

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 In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem, proved by Thomas Jerome Schaefer, states necessary and sufficient conditions under which a finite set ''S'' of relations over the Boolean domain yields ...

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

, and decision versions of factoring and the

discrete logarithm In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...

. Under the exponential time hypothesis, there exist natural problems that require quasi-polynomial time, and can be solved in that time, including finding a large disjoint set of

unit disk In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1: :D_1(P) = \.\, The closed unit disk around ''P'' is the set of points whose d ...

s from a given set of disks in the

hyperbolic plane In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P' ...

, and finding a graph with few vertices that is not an

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

of a given graph. The exponential time hypothesis also implies that no quasi-polynomial-time problem can be NP-complete, so under this assumption these problems must be NP-intermediate.

List of problems that might be NP-intermediate

Algebra and number theory

* A decision version of factoring integers: for input

n

and

k

, does

n

have a factor in the interval

,k /math>?
* Decision versions of the

discrete logarithm problem In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...

and others related to cryptographic assumptions * 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) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

for "intersecting monotone CNF":

conjunctive normal form In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. In au ...

, 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: given the truth table of a Boolean function and positive integer

s

, does there exist a circuit of size at most

s

for this function? * Monotone dualization: given CNF and DNF formulas for monotone Boolean functions, do they represent the same function? * 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

* Determining whether the

rotation distance In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial e ...

between two

binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...

s or the flip distance between two triangulations of the same convex polygon is below a given threshold * The turnpike problem of reconstructing points on line from their distance multiset * The

cutting stock problem In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of Inventory, stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimizat ...

with a constant number of object lengths * Knot triviality * Finding a simple closed quasigeodesic on a convex polyhedron

Game theory

* Determining the winner in

parity game A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The ow ...

s, 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 c ...

* Finding a graph's automorphism group * Finding the number of graph automorphisms * Planar minimum bisection * Deciding whether a graph admits a

graceful labeling In graph theory, a graceful labeling of a Graph (discrete mathematics), graph with edges is a graph labeling, labeling of its Vertex (graph theory), vertices with some subset of the integers from 0 to inclusive, such that no two vertices share ...

* Recognizing leaf powers and -leaf powers * Recognizing graphs of bounded

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of ...

* Testing the existence of a

simultaneous embedding Simultaneous embedding is a technique in graph drawing and information visualization for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between ...

with fixed edges

Miscellaneous

* Testing whether the Vapnik–Chervonenkis dimension of a given family of sets is below a given bound

References

External links

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