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 [2,k]?
• Decision versions of the discrete logarithm problem and others related to cryptographic assumptions
• Linear divisibility: given integers x and y, does y have a divisor congruent to 1 modulo x?{{cite conference

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{{cite conference | editor1-last = Flesca | editor1-first = Sergio | editor2-last = Greco | editor2-first = Sergio | editor3-last = Leone | editor3-first = Nicola | editor4-last = Ianni | editor4-first = Giovambattista
• 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?{{cite conference | doi-access =free
• 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?{{cite journal

Computational geometry and computational topology

• Determining whether the rotation distance{{cite journal
• The turnpike problem of reconstructing points on line from their distance multiset{{cite conference | editor-last = Seidel | editor-first = Raimund
• The cutting stock problem with a constant number of object lengths{{cite journal
• Knot triviality{{cite journal
• Finding a simple closed quasigeodesic on a convex polyhedron{{cite book | title-link=Geometric Folding Algorithms

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{{cite journal
• 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.{{cite journal

Graph algorithms

• Graph isomorphism problem{{cite book
• Finding a graph's automorphism group
• Finding the number of graph automorphisms
• Planar minimum bisection{{cite conference | editor1-last = Diks | editor1-first = Krzysztof | editor2-last = Rytter | editor2-first = Wojciech
• Deciding whether a graph admits a graceful labeling{{cite journal
• Recognizing leaf powers and k-leaf powers{{cite journal
• Recognizing graphs of bounded clique-width{{cite journal
• Testing the existence of a simultaneous embedding with fixed edges{{cite conference | access-date = 2019-09-10 | archive-date = 2021-10-22 | archive-url = https://web.archive.org/web/20211022062107/http://e-archive.informatik.uni-koeln.de/507/2/zaik2006-507.pdf | url-status = dead

Miscellaneous

• Testing whether the Vapnik–Chervonenkis dimension of a given family of sets is below a given bound{{cite journal

References

References

1. (2007). "Finite model theory and its applications". [[Springer-Verlag]].
2. Schaefer, Thomas J.. (1978). "Proc. 10th Ann. ACM Symp. on Theory of Computing".
3. Papadimitriou, Christos H.. (1994). "Computational Complexity". Addison-Wesley.
4. (1979). "A note on the graph isomorphism counting problem". [[Information Processing Letters]].