NP-intermediate

• 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

| last1 = Adleman | first1 = Leonard

| last2 = Manders | first2 = Kenneth

| contribution = Reducibility, randomness, and {{not a typo|intractibility}}

| doi = 10.1145/800105.803405

| title = Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77)

| year = 1977}}{{cite book|title=Computational Complexity|first=Christos H.|last=Papadimitriou|publisher=Addison-Wesley|year=1994|isbn= 9780201530827|page=236}}

• 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

| last1 = Eiter | first1 = Thomas

| last2 = Gottlob | first2 = Georg

| editor1-last = Flesca | editor1-first = Sergio

| editor2-last = Greco | editor2-first = Sergio

| editor3-last = Leone | editor3-first = Nicola

| editor4-last = Ianni | editor4-first = Giovambattista

| contribution = Hypergraph transversal computation and related problems in logic and AI

| doi = 10.1007/3-540-45757-7_53

| pages = 549–564

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings

| volume = 2424

| year = 2002}}

• 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

| first1 =Valentine

| last1 =Kabanets

| first2 =Jin-Yi

| last2 =Cai

| contribution = Circuit minimization problem

| title = Proc. 32nd Symposium on Theory of Computing

| id = {{ECCC|1999|99|045}}

| year =2000

| pages =73–79

| place = Portland, Oregon, USA

| doi = 10.1145/335305.335314| title-link =Symposium on Theory of Computing

| s2cid =785205

| 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

| last1 = Eiter | first1 = Thomas

| last2 = Makino | first2 = Kazuhisa

| last3 = Gottlob | first3 = Georg

| doi = 10.1016/j.dam.2007.04.017 | doi-access=free

| issue = 11

| journal = Discrete Applied Mathematics

| mr = 2437000

| pages = 2035–2049

| title = Computational aspects of monotone dualization: a brief survey

| volume = 156

| year = 2008| s2cid = 10096898

}}

• Determining whether the rotation distance{{cite journal

| last1 = Sleator | first1 = Daniel D.

| last2 = Tarjan | first2 = Robert E.

| last3 = Thurston | first3 = William P.

| doi = 10.2307/1990951 | doi-access=free

| issue = 3

| journal = Journal of the American Mathematical Society

| mr = 928904

| pages = 647–681

| title = Rotation distance, triangulations, and hyperbolic geometry

| volume = 1

| year = 1988| jstor = 1990951

}} 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{{cite conference

| last1 = Skiena | first1 = Steven

| last2 = Smith | first2 = Warren D.

| last3 = Lemke | first3 = Paul

| editor-last = Seidel | editor-first = Raimund

| contribution = Reconstructing Sets from Interpoint Distances (Extended Abstract)

| doi = 10.1145/98524.98598

| pages = 332–339

| publisher = ACM

| title = Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990

| year = 1990| doi-access = free

}}

• The cutting stock problem with a constant number of object lengths{{cite journal

| last1 = Jansen | first1 = Klaus

| last2 = Solis-Oba | first2 = Roberto

| doi = 10.1287/moor.1110.0515

| issue = 4

| journal = Mathematics of Operations Research

| mr = 2855867

| pages = 743–753

| title = A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths

| volume = 36

| year = 2011}}

• Knot triviality{{cite journal

| last = Lackenby | first = Marc

| arxiv = 1604.00290

| doi = 10.1016/j.aim.2021.107796 | doi-access=free

| journal = Advances in Mathematics

| mr = 4274879

| page = Paper No. 107796

| title = The efficient certification of knottedness and Thurston norm

| volume = 387

| year = 2021| s2cid = 119307517

}}

• Finding a simple closed quasigeodesic on a convex polyhedron{{cite book

| last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine

| last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor)

| contribution = 24 Geodesics: Lyusternik–Schnirelmann

| doi = 10.1017/CBO9780511735172

| isbn = 978-0-521-71522-5

| location = Cambridge

| mr = 2354878

| pages = 372–375

| publisher = Cambridge University Press

| title = Geometric folding algorithms: Linkages, origami, polyhedra

| title-link=Geometric Folding Algorithms

| year = 2007}}.

• 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

| last = Jurdziński | first = Marcin

| doi = 10.1016/S0020-0190(98)00150-1

| issue = 3

| journal = Information Processing Letters

| mr = 1657581

| pages = 119–124

| title = Deciding the winner in parity games is in UP $\backslash cap$ co-UP

| volume = 68

| year = 1998}}

• 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

| last = Condon | first = Anne

| doi = 10.1016/0890-5401(92)90048-K

| issue = 2

| journal = Information and Computation

| mr = 1147987

| pages = 203–224

| title = The complexity of stochastic games

| volume = 96

| year = 1992| doi-access = free

}}

• Graph isomorphism problem{{cite book

| last1 = Grohe | first1 = Martin

| last2 = Neuen | first2 = Daniel

| arxiv = 2011.01366

| contribution = Recent advances on the graph isomorphism problem

| date = June 2021

| doi = 10.1017/9781009036214.006

| pages = 187–234

| publisher = Cambridge University Press

| title = Surveys in Combinatorics 2021| s2cid = 226237505

}}

• Finding a graph's automorphism group
• Finding the number of graph automorphisms{{cite journal | last1 = Mathon | first1 = R. | year = 1979 | title = A note on the graph isomorphism counting problem | journal = Information Processing Letters | volume = 8 | issue = 3 | pages = 131–132 | doi=10.1016/0020-0190(79)90004-8}}
• Planar minimum bisection{{cite conference

| last = Karpinski | first = Marek

| editor1-last = Diks | editor1-first = Krzysztof

| editor2-last = Rytter | editor2-first = Wojciech

| contribution = Approximability of the minimum bisection problem: an algorithmic challenge

| doi = 10.1007/3-540-45687-2_4

| pages = 59–67

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings

| volume = 2420

| year = 2002}}

• Deciding whether a graph admits a graceful labeling{{cite journal

| last = Gallian | first = Joseph A.

| date = December 17, 2021

| journal = Electronic Journal of Combinatorics

| mr = 1668059

| page = Dynamic Survey 6

| title = A dynamic survey of graph labeling

| url = https://www.combinatorics.org/Surveys/index.html

| volume = 5}}

• Recognizing leaf powers and {{mvar|k}}-leaf powers{{cite journal

| last1 = Nishimura | first1 = N.

| last2 = Ragde | first2 = P.

| last3 = Thilikos | first3 = D.M.

| journal = Journal of Algorithms

| pages = 69–108

| title = On graph powers for leaf-labeled trees

| volume = 42

| year = 2002 | doi=10.1006/jagm.2001.1195}}.

• Recognizing graphs of bounded clique-width{{cite journal

| last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows

| last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond

| last3 = Rotics | first3 = Udi

| last4 = Szeider | first4 = Stefan | author4-link = Stefan Szeider

| doi = 10.1137/070687256

| issue = 2

| journal = SIAM Journal on Discrete Mathematics

| mr = 2519936

| pages = 909–939

| title = Clique-width is NP-complete

| volume = 23

| year = 2009}}.

• Testing the existence of a simultaneous embedding with fixed edges{{cite conference

| last1 = Gassner | first1 = Elisabeth

| last2 = Jünger | first2 = Michael

| last3 = Percan | first3 = Merijam

| last4 = Schaefer | first4 = Marcus

| last5 = Schulz | first5 = Michael

| contribution = Simultaneous graph embeddings with fixed edges

| doi = 10.1007/11917496_29

| mr = 2290741

| pages = 325–335

| publisher = Springer | location = Berlin

| series = Lecture Notes in Computer Science

| title = Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers

| volume = 4271

| year = 2006| url = http://e-archive.informatik.uni-koeln.de/507/2/zaik2006-507.pdf

}}.

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

| last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou

| last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis

| doi = 10.1006/jcss.1996.0058

| issue = 2, part 1

| journal = Journal of Computer and System Sciences

| mr = 1418886

| pages = 161–170

| title = On limited nondeterminism and the complexity of the V-C dimension

| volume = 53

| year = 1996| doi-access = free

}}

{{Reflist|30em}}

• {{ComplexityZoo|Class NPI|N#npi}}
• [https://web.archive.org/web/20110727222854/http://users.comlab.ox.ac.uk/luke.ong/teaching/complexity/section5.ps Basic structure, Turing reducibility and NP-hardness]
• {{Cite web

|author=Lance Fortnow

|url=http://oldblog.computationalcomplexity.org/archive/2003_03_23_archive.html#200039297

|title=Foundations of Complexity, Lesson 16: Ladner's Theorem

|accessdate=1 November 2013

|date=24 March 2003}}

{{DEFAULTSORT:Np-Intermediate}}

Category:Complexity classes