NP-intermediate

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, Ring isomorphism, Ring automorphism
• 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
• Recognizing leaf powers and -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