Rahul Sharma (Editor)

NP intermediate

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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, it follows that P = NP if and only if NPI is empty.

Contents

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 can not be in NPI. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.

Algebra and number theory

  • Factoring integers
  • Discrete Log Problem and others related to cryptographic assumptions
  • Isomorphism problems: Group isomorphism problem, Group automorphism, Ring isomorphism, Ring automorphism
  • Determining the result of a comparison between two sums of square roots of integers
  • Numbers in boxes problems
  • The linear divisibility problem

    • Boolean logic

  • Intersecting Monotone SAT
  • Minimum Circuit Size Problem
  • Monotone self-duality

    • 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
  • Deciding whether a given triangulated 3-manifold is a 3-sphere
  • Gap version of the closest vector in lattice problem
  • Finding a simple closed quasigeodesic on a convex polyhedron

    • Game theory

  • Determining winner in parity games
  • Determining who has the highest chance of winning a stochastic game
  • Agenda control for balanced single-elimination tournaments

    • Graph algorithms

  • Graph isomorphism problem
  • Planar minimum bisection
  • Deciding whether a graph admits a graceful labeling
  • Clustered planarity
  • Recognizing leaf powers and k-leaf powers
  • Recognizing graphs of bounded clique-width
  • Finding a simultaneous embedding with fixed edges

    • Miscellaneous

  • Assuming NEXP is not equal to EXP, padded versions of NEXP-complete problems
  • Problems in TFNP
  • Pigeonhole subset sum
  • Finding the VC dimension

    • References

    NP-intermediate Wikipedia
    (Text) CC BY-SA