NP-intermediate

In

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.^[2][3] Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, and decision versions of factoring and the discrete logarithm.

List of problems that might be NP-intermediate

Algebra and number theory

• A decision version of
  factoring integers
  : for input ${\displaystyle n}$ and ${\displaystyle k}$, does ${\displaystyle n}$ have a factor in the interval ${\displaystyle [2,k]}$?
• Decision versions of the
  discrete logarithm problem
  and others related to cryptographic assumptions
• Linear divisibility: given integers ${\displaystyle x}$ and ${\displaystyle y}$, does ${\displaystyle y}$ have a divisor congruent to 1 modulo ${\displaystyle x}$?^[4][5]

Boolean logic

• IMSAT, the Boolean satisfiability problem 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^[6]
• Minimum circuit size problem
  : given the truth table of a Boolean function and positive integer ${\displaystyle s}$, does there exist a circuit of size at most ${\displaystyle s}$ for this function?^[7]
• Monotone dualization: given CNF and DNF formulas for monotone Boolean functions, do they represent the same function?^[8]
• 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?^[8]

Computational geometry and computational topology

• Determining whether the rotation distance^[9] between two binary trees 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^[10]
• The cutting stock problem with a constant number of object lengths^[11]
• Knot triviality^[12]
• Finding a simple closed quasigeodesic on a convex polyhedron^[13]

Game theory

• Determining the 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^[14]
• 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.^[15]

Graph algorithms

• Graph isomorphism problem^[16]
• Planar minimum bisection^[17]
• Deciding whether a graph admits a graceful labeling^[18]
• Recognizing leaf powers and k-leaf powers^[19]
• Recognizing graphs of bounded clique-width^[20]
• Testing the existence of a simultaneous embedding with fixed edges^[21]

Miscellaneous

• Testing whether the Vapnik–Chervonenkis dimension of a given family of sets is below a given bound^[22]

References