<p><strong>The sums of square roots problem:</strong> Given two sequences <span class="math-container">$a_1, a_2, \dots, a_n$</span> and <span class="math-container">$b_1, b_2, \dots, b_n$</span> of positive integers, is <span class="math-container">$A := \sum_i \sqrt{a_i}$</span> less than, equal to, or greater than <span class="math-container">$B := \sum_i \sqrt{b_i}$</span>?</p>
<ul>
<li><p>The problem has a trivial <span class="math-container">$O(n)$</span>-time algorithm on the real RAM—Just compute the sums and compare them!—but this does not imply membership in P.</p>
</li>
<li><p>There is an obvious finite-precision algorithm, but it is not known whether a polynomial number of bits of precision is sufficient for correctness.  (See <a href="https://topp.openproblem.net/p33" rel="noreferrer">https://topp.openproblem.net/p33</a> for details.)</p>
</li>
<li><p>The Pythogorean theorem implies that the length of any polygonal curve whose vertices and integer endpoints is a sum of square roots of integers.  Thus, the sum-of-roots  problem is inherent in several planar computational geometry problems, including <a href="http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree" rel="noreferrer">Euclidean minimum spanning trees</a>, <a href="http://en.wikipedia.org/wiki/Euclidean_shortest_path" rel="noreferrer">Euclidean shortest paths</a>, <a href="http://en.wikipedia.org/wiki/Minimum-weight_triangulation" rel="noreferrer">minimum-weight triangulations</a>, and the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem#With_metric_distances" rel="noreferrer">Euclidean traveling salesman problem</a>.  (The Euclidean MST problem can be solved in polynomial time without resolving the sum-of-roots problem, thanks to the underlying matroid structure and the fact that the EMST is a subgraph of the Delaunay triangulation.)</p>
</li>
<li><p>There <em>is</em> a polynomial-time randomized algorithm, <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1991.185434" rel="noreferrer">due to Johannes Blömer</a>, to decide whether the two sums are equal.  However, if the answer is no, Blömer's algorithm does not determine which sum is larger.</p>
</li>
<li><p>The decision version of this problem (Is <span class="math-container">$A &gt; B$</span>?) is not even known to be in NP.  However, Blömer's algorithm implies that if the decision problem is in NP, then it is also in co-NP.  Thus, the problem is unlikely to be NP-complete.</p>
</li>
</ul>

CC BY-SA 3.0
2016-09-11T19:30:22.753Z
Well, if we take just 1000 random integers, not too large, then there are about $2^{999}$ ways to divide them into two sets, so I would expect that two of these sums are within 900 or more bits within each other (and within half of the total sum). On the other hand, finding the "worst" two sequences to compare out of these $2^{999}$ possibilities is also very, very hard.
gnasher729
CC BY-SA 4.0
2024-06-10T19:16:16.817Z
The question asks for a problem in NP, but this answer says the problem is not known to be in NP?
A. Rex
CC BY-SA 4.0
2010-12-29T06:22:36.717Z
2021-09-17T22:49:19.800Z
2021-09-17T22:49:19.800Z
Jeffε
<p>My favorite problem in this class (I'll phrase it as a functional problem, but it's easy to turn into a decision problem in the standard way): compute the rotation distance between two binary trees (equivalently, the flip distance between two triangulations of a convex polygon).</p>

CC BY-SA 4.0
2018-08-22T00:33:42.220Z
See also "*A Note on the Flip Distance Problem for Edge-Labeled Triangulations*" ([Arxiv, 2018](https://arxiv.org/abs/1808.03126)).
Neal Young
CC BY-SA 2.5
2010-11-02T22:39:51.620Z
Interesting. Exploring the rotation space is also an active area of research it seems. "The rotation graph of k-ary trees is Hamiltonian", IPL 2008, http://dx.doi.org/10.1016/j.ipl.2008.09.013
Chad Brewbaker
CC BY-SA 2.5
2010-08-17T03:29:06.223Z
That's a neat problem: I didn't realize it was in limbo.
Suresh Venkat
CC BY-SA 2.5
2010-08-17T05:21:26.800Z
Yeah I didn't know about it either! For all these problems/answers, I wonder if  they are in Limbo because we think they really are or if they're more like PRIMES...
Lev Reyzin
CC BY-SA 2.5
2010-08-17T05:32:58.217Z
This problem and its potentially intermediate status should be more well-known.  Can you give a reference to it?  Also, is there any result indicating that it is not NP-complete, as there is for Graph Isomorphism and related problems?
Joshua Grochow
CC BY-SA 2.5
2010-08-17T06:01:28.890Z
A very pretty and important but older reference is Thurston, Sleator, and Tarjan, "Rotation distance, triangulations, and hyperbolic geometry", STOC'86 and JAMS'88. For a recent reference that explicitly mentions the complexity of the problem as still being open, see Lucas, "An improved kernel size for rotation distance in binary trees", IPL 2010, http://dx.doi.org/10.1016/j.ipl.2010.04.022
David Eppstein
CC BY-SA 2.5
2010-08-17T03:18:17.120Z
2010-08-17T03:18:17.120Z
David Eppstein
<p>A problem that is mentioned neither in this list or the MO list is the turnpike problem. Given a multiset of n(n-1)/2 numbers, each number representing the distance between two points on the line, reconstruct the positions of the original points. </p>

<p>Note that what makes this nontrivial is that for a given number d in the multiset, you don't know which pair of points is d units apart. </p>

<p><a href="http://portal.acm.org/citation.cfm?id=98598&amp;dl=GUIDE,">While it is known</a> that for any given instance there are only a polynomial number of solutions, it is not known how to find one ! </p>

CC BY-SA 3.0
2017-12-24T18:58:03.543Z
@SureshVenkat this is awesome, reminds me of [Golomb Rulers](https://en.wikipedia.org/wiki/Golomb_ruler).  What is the "factoring" problem to which you refer? Are the coefficients of the polynomial in $x^i$ the multiset values at $i$? Would this, then, be amenable to [Shor's](https://en.wikipedia.org/wiki/Shor%27s_algorithm) algorithm on a quantum computer?
Mark S
CC BY-SA 2.5
2010-10-26T22:02:50.693Z
You encounter a similar problem in bioinformatics: Given a set of potentially/hopefully overlapping, randomly created substrings of a string much longer than the individual pieces; compute the original string. (gene sequencing)
Raphael
CC BY-SA 2.5
2010-08-17T05:18:28.273Z
Thanks - this is a good one!  Reminds me of some other "localization" problems.  Is it actually thought to be not in p?
Lev Reyzin
CC BY-SA 2.5
2010-08-17T05:22:58.687Z
I am not aware that turnpike is directly linked to known problems in complexity. However, there's a "wrong direction" relation to factoring, in that the turnpike problem cam be phrased as a factoring problem on an appropriately chosen polynomial.
Suresh Venkat
CC BY-SA 2.5
2010-08-17T05:37:39.877Z
Are there known unlikely consequences of this problem being NP-complete, as there are for Graph Isomorphism (PH collapsing)?
Joshua Grochow
CC BY-SA 2.5
2010-08-17T05:46:31.497Z
not that I'm aware of. it hasn't been studied that much, which is a pity, because it's so natural.
Suresh Venkat
CC BY-SA 2.5
2010-08-17T03:32:35.633Z
2010-08-17T03:32:35.633Z
Suresh Venkat
<p>Here is a list of problems that may or may not qualify as "sufficiently" different.  By the same proof as for Graph Isomorphism, if any of them is NP-complete, then the Polynomial Hierarchy collapses to the second level.  I do not think there is any broad consensus as to which of these "ought" to be in P.</p>

<ul>
<li>Graph Automorphism (determine if a graph has a nontrivial automorphism).  Reduces to Graph Isomorphism, but not known (not thought?) to be GI-hard.</li>
<li>Group Isomorphism and Automorphism (where the groups are given by their multiplication tables).  Again, reduces to Graph Isomorphism, but not thought to be GI-hard.</li>
<li>Ring Isomorphism and Automorphism.  In a sense, this is the grand-daddy of all the above problems, since integer factoring is equivalent to finding a nontrivial automorphism of a ring, and Graph Isomorphism reduces to Ring Isomorphism.  See <a href="http://dimacs.rutgers.edu/~kayaln/pdf/ringAuto_journal.pdf">Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems.
Computational Complexity 15(4): 342-390 (2006).</a>  (Interestingly, <em>determining</em> if a ring has a nontrivial automorphism is in $P$.)</li>
<li><a href="http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html">This post</a> by Bill Gasarch contains some other problems with the taste of Ramsey theory that look like they might be intermediate.</li>
<li>By Mahaney's Theorem, no sparse set can be NP-complete.  But we also know that there are sparse sets in $NP$ - $P$ iff $NEXP$ is not equal to $EXP$.  So assuming $NEXP \neq EXP$, the padded version of any $NEXP$-complete problem is of intermediate complexity.  (Such a set cannot be in $P$ unless $NEXP = EXP$, contradicting our assumption.)  There are plenty of natural $NEXP$-complete problems.</li>
</ul>

CC BY-SA 2.5
2010-08-17T03:16:06.137Z
I like the last example. Do you have any references about it?
Marcos Villagra
CC BY-SA 2.5
2010-08-17T04:02:54.713Z
S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.  http://dx.doi.org/10.1016/0022-0000(82)90002-2

Sparse sets in NP - P iff NEXP neq EXP: 

J. Hartmanis, N. Immerman, V. Sewelson, Sparse sets in NP-P: EXPTIME versus NEXPTIME, Information and Control, Volume 65, Issues 2-3, May-June 1985, Pages 158-181.  http://dx.doi.org/10.1016/S0019-9958(85)80004-8
Joshua Grochow
CC BY-SA 2.5
2010-08-17T19:46:36.630Z
This is a nice list, though the first three are quite similar :)  I like the last example as well.
Lev Reyzin
CC BY-SA 2.5
2010-08-17T03:12:24.760Z
2010-08-24T01:19:50.483Z
2010-08-24T01:19:50.483Z
Joshua Grochow
<p>The Minimum Circuit Size Problem (MCSP) is my favorite "natural" problem in NP that's not known to be NP-complete: Given the truth-table (of size n=2^m) of an m-variate Boolean function f, and given a number s, does f have a circuit of size s?  If MCSP is easy, then there is no cryptographically-secure one-way function.  This problem and its variants provided much of the motivation for the study of "brute-force" algorithms in Russia, leading to Levin's work on NP-completeness.  This problem can also be viewed in terms of resource-bounded Kolmogorov complexity: asking if a string can be recovered quickly from a short description.  This version of the problem was studied by Ko; the name MCSP was used first by Cai and Kabanets, as far as I know.  More references can be found in some papers of mine:
<a href="http://ftp.cs.rutgers.edu/pub/allender/KT.pdf">http://ftp.cs.rutgers.edu/pub/allender/KT.pdf</a>
http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf </p>

CC BY-SA 2.5
2010-09-28T09:55:04.623Z
2010-09-28T09:55:04.623Z
Eric Allender
<p><strong>Monotone self-duality</strong></p>

<p>For any boolean function <span class="math-container">$f=f(x_1, x_2, ..., x_n)$</span>, it's dual is <span class="math-container">$f^d=\bar{f}(\bar{x_1}, \bar{x_2}, ..., \bar{x_n})$</span>. Given <span class="math-container">$f(x_1, x_2, ..., x_n)$</span> represented by a CNF formula, we have to decide whether <span class="math-container">$f=f^d$</span>.   </p>

<p>This problem is in co-NP[<span class="math-container">$\log^2 n$</span>], i.e., it is decidable with <span class="math-container">$O(\log^2n/ \log\log n)$</span> nondeterministic steps. Thus, it has a quasi-polynomial time algorithm (<span class="math-container">$O(n^{\log n/\log \log n})$</span> time), and hence is unlikely to be co-NP-hard. </p>

<p>It is still open whether this problem is in P or not. More details can be found in the 2008 paper "<a href="http://dx.doi.org/10.1016/j.dam.2007.04.017" rel="nofollow noreferrer">Computational aspects of monotone dualization: A brief survey</a>" by Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. </p>

CC BY-SA 4.0
2010-12-23T00:47:34.333Z
2018-11-27T12:17:17.653Z
2018-11-27T12:17:17.653Z
Dan
<p>Knot triviality: Given a closed polygonal chain in 3-space, is it unknotted (ie, ambient-isotopic to a flat circle)?</p>

<p>This is known to be in NP by deepish results in normal surface theory, but no poly-time algorithm or NP-hardness proof is known.</p>

CC BY-SA 3.0
2017-12-24T19:11:43.527Z
Since the time this answer was first posted, Kuperberg [placed](https://arxiv.org/abs/1112.0845) it in $\mathsf{coNP}$ conditional on the Generalized Riemann Hypothesis, and Lackenby [placed](https://arxiv.org/abs/1302.0180) it unconditonally in $\mathsf{coNP}$.
Mark S
CC BY-SA 2.5
2010-10-25T02:45:53.267Z
It might be worth mentioning that, as with many potentially NP-intermediate problems, a slight variant is known to be NP-complete. Namely, 3-manifold knot genus is NP-complete: given a closed polygonal chain in a triangulated 3-manifold and an integer g, is the knot the boundary of a surface of genus at most g? (Being the unknot is equivalent to genus 0.) http://doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016
Joshua Grochow
CC BY-SA 2.5
2010-10-29T04:13:49.873Z
It's also contained in co-AM (Hara, Tani, Yamamoto), so not NPC unless the polynomial hierarchy collapses.
Peter Shor 
CC BY-SA 2.5
2010-10-29T05:55:27.180Z
Actually, that's still open.  Tasos Sidiropoulos found a bug in the Hara-Tani-Yamamoto proof.
Jeffε
CC BY-SA 2.5
2010-09-09T01:16:44.677Z
2010-09-09T01:16:44.677Z
Jeffε
<p>In a <em>monotone</em> CNF formula every clause contains only positive literals or only negative literals.  In an <em>intersecting</em> monotone CNF formula every positive clause has some variable in common with every negative clause.</p>

<p>The decision problem</p>

<blockquote>
  <p><strong>INTERSECTING MONOTONE SAT</strong><br>
  <em>Input:</em> intersecting monotone CNF formula $f$<br>
  <em>Question:</em> is $f$ satisfiable?</p>
</blockquote>

<p>has an $n^{o(\log\ n)}$ algorithm dating back to 1996, but is not known to be in P.  (Of course, it might turn out to be in P, but that would be a major result.)</p>

<ul>
<li>Thomas Eiter and Georg Gottlob, <em>Hypergraph Transversal Computation and Related Problems in Logic and AI</em>, JELIA 2002.  doi: <a href="http://10.1007/3-540-45757-7_53">10.1007/3-540-45757-7_53</a></li>
</ul>

CC BY-SA 2.5
2010-09-27T21:19:06.673Z
2010-09-27T21:19:06.673Z
András Salamon
<p>It is not known if it is possible to decide in polynomial time if player 1 has a winning strategy in a parity game (from a given starting position). The problem is, however, contained in NP and co-NP and even in UP and co-UP.</p>

CC BY-SA 2.5
2010-12-23T00:52:48.870Z
The recent paper "A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information" also shows that even a generalization of the parity game can be solved in pseudo-polynomial time. In particular, they show that a game called BWR game has a pseudo-polynomial time algorithm when there is a constant number of "random nodes". The parity game is the case where there is no random nodes.
Dan
CC BY-SA 3.0
2017-03-12T21:28:00.517Z
It was shown recently that parity games can be solved in quasipolynomial time, see [here](http://cs.stackexchange.com/questions/16399/is-it-possible-to-solve-parity-game-problem-in-polynomial-time/71442#71442) for example.
Thomas Klimpel
CC BY-SA 2.5
2010-08-17T15:11:00.133Z
Can you give a reference?  Sounds interesting.
Joshua Grochow
CC BY-SA 2.5
2010-08-17T16:43:24.597Z
M. Jurdzinski. Deciding the Winner in Parity Games is in UP \cap co-Up. Information Processing Letters 68(3):119-124. 1998. Should at least be a good starting point.
Matthias
CC BY-SA 2.5
2010-08-17T12:55:31.840Z
2010-08-17T12:55:31.840Z
Matthias
<p><a href="http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality" rel="noreferrer">The Pigeonhole Version of Subset Sum</a> (or Subset Sum Equality).</p>

<p>Given:</p>

<p>$$a_k \in \mathbb{Z}_{&gt;0}$$
$$\sum_{k=0}^{n-1} a_k &lt; 2^n - 1$$</p>

<p>By the pigeonhole principle, there must exist two disjoint subsets, $S_1, S_2 \subseteq \{ 1, \dots, n \} $ such that:</p>

<p>$$\sum_{j \in S_1} a_j = \sum_{k \in S_2} a_k $$</p>

<p>The pigeonhole subset sum problem asks for such a solution.  Originally stated in "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.1192&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem</a>" by Bazgan, Santha and Tuza.</p>

CC BY-SA 3.0
2010-12-28T05:21:37.970Z
2014-03-04T20:38:40.397Z
2014-03-04T20:38:40.397Z
user834
<p>You get a very long list of problems if willing to accept approximation problems, such as approximating Max-Cut to within a factor 0.878. We don't know if it's NP-hard or in P (only know NP-hardness assuming the Uniuqe Games Conjecture).</p>

CC BY-SA 2.5
2010-08-17T02:44:01.300Z
Yes, that was a silly comment that I started to delete as soon as it was posted. Thank you. :)
Daniel Apon
CC BY-SA 2.5
2010-08-17T03:07:22.990Z
Thanks! But I guess I wasn't thinking as much about approximation problems, but more of natural problems.
Lev Reyzin
CC BY-SA 2.5
2010-08-17T03:15:42.530Z
Arguably, these are natural problems since they correspond to what is achievable by a natural set of techniques, in this case, semidefinite programming.
Moritz
CC BY-SA 2.5
2010-08-17T05:23:38.060Z
I guess "natural" is a vague criterion...
Lev Reyzin
CC BY-SA 2.5
2010-08-17T02:12:14.060Z
2010-08-17T02:12:14.060Z
Moritz
<p>Is a given triangulated 3-manifold a 3-sphere? <a href="https://cstheory.stackexchange.com/questions/2429/is-the-3-sphere-recognition-problem-np-complete">From Joe O'Rourke.</a></p>

CC BY-SA 2.5
2010-10-26T21:16:49.390Z
2010-10-26T21:16:49.390Z
2017-04-13T12:32:28.117Z
Peter Shor 
<p>There are a lot of problems related to finding hidden subgroups. You mentioned factoring, but there is also the discrete log problem as well as others related to elliptic curves, etc.</p>

CC BY-SA 2.5
2010-08-17T03:16:41.550Z
2010-08-17T03:16:41.550Z
Joe Fitzsimons
<p>Take a look at the class <a href="http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf">TFNP</a>. It has a lot of search problems with an intermediate status.</p>

CC BY-SA 2.5
2010-08-17T03:08:27.683Z
I should point out that it is the class of related function problems in $NP\cap coNP$.
Marcos Villagra
CC BY-SA 2.5
2010-08-17T03:07:32.600Z
2010-08-17T03:07:32.600Z
Marcos Villagra
<p>The induced subgraph isomorphism problem has NP-incomplete &quot;left-hand side restrictions&quot; assuming that P is not equal to NP. See Y. Chen, M. Thurley, M. Weyer: <a href="http://dx.doi.org/10.1007/978-3-540-70575-8_48" rel="noreferrer">Understanding the Complexity of Induced Subgraph Isomorphisms</a>, ICALP 2008.</p>

CC BY-SA 2.5
2010-08-19T02:50:30.450Z
Although this is an interesting result, if you check the paper it even says that the proof of intermediate complexity is essentially the same as Ladner's Theorem, except you do the diagonalization in the choice of the LHS restriction.  So I don't know if this counts as a "natural" problem, rather than just a different encoding of Ladner's Theorem.
Joshua Grochow
CC BY-SA 2.5
2010-09-22T14:59:35.720Z
Note also that these are source-and-target restrictions.  The target (right hand side) has to be of special form, to enforce injectivity.
András Salamon
CC BY-SA 2.5
2010-08-17T09:17:04.140Z
2010-08-17T09:17:04.140Z
2020-06-17T09:38:08.363Z
Holger
<p>The complexity of planar Minimum Bisection problem is an intriguing open problem which is not known to be $NP$-hard. In contrast, the planar Maximum Bisection problem is $NP$-hard. </p>

<p>Minimum Bisection problem: Find a partition of the set of nodes into two equal size parts such that the number of crossing edges is minimized.</p>

<p><a href="http://portal.acm.org/citation.cfm?id=668338">Karpinski, Approximability of the Minimum Bisection Problem: An Algorithmic Challenge </a></p>

CC BY-SA 2.5
2010-12-23T17:14:51.677Z
do you have a reference to the problem definition?
Lev Reyzin
CC BY-SA 2.5
2010-12-23T19:19:12.673Z
Reference is added.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-23T16:39:49.313Z
2010-12-24T20:14:38.837Z
2010-12-24T20:14:38.837Z
Mohammad Al-Turkistany
<p>Here's a problem in computational social choice which is not known to be in P, and may or may not be NP-complete.</p>

<p>Agenda control for balanced single-elimination tournaments:</p>

<p>Given: tournament graph $T$ on $n=2^k$ nodes, node $a$</p>

<p>Question: does there exist a permutation of the nodes (a <em>bracket</em>) so that a is the winner of the induced single-elimination tournament?</p>

<p>Given a permutation $P_k$ on $2^k$ nodes of $V$ and a tournament graph $T$ on $V$, one can obtain a permutation $P_{k-1}$ on $2^{k-1}$ nodes as follows. For every $i>0$, consider $P_k[2i-1]$ and $P_k[2i]$ and the arc $e$ between them in $T$; let $P_{k-1}[i]=P_k[2i-1]$ if $e=(P_k[2i-1],P_k[2i])$ and $P_{k-1}[i]=P_k[2i]$ otherwise.
That is, we match up pairs of nodes according to $P_k$ and use $T$ to decide which nodes (winners) move on to the next round $P_{k-1}$. Hence given a permutation on $2^k$ one can actually define $k$ rounds $P_{k-1},\ldots,P_0$ inductively as above, until the last permutation contains only one node. This defines a (balanced) single-elimination tournament on $2^k$ nodes. The node which remains after all the rounds is the winner of the tournament.</p>

<p>Agenda control for balanced single-elimination tournaments (graph formulation):</p>

<p>Given: tournament graph $T$ on $n=2^k$ nodes, node $a$</p>

<p>Question: does $T$ contain a (spanning) binomial arborescence on $2^k$ nodes rooted at $a$?</p>

<p>A binomial arborescence on $2^k$ nodes rooted at a node $x$ is defined recursively as $a$ binomial arborescence on $2^{k-1}$ nodes rooted at $x$ and a binomial arborescence on $2^{k-1}$ nodes rooted at a different node $y$ and an arc from $x$ to $y$. (If $k=0$, a binomial arborescence is just the root.) The spanning binomial arborescences in a tournament graph capture exactly the single-elimination tournaments which can be played, given the match outcome information in the tournament graph.</p>

<p>Some references:</p>

<ol>
<li>Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: Winner Determination in Sequential Majority Voting. IJCAI 2007: 1372-1377.</li>
<li>N. Hazon, P. E. Dunne, S. Kraus, and , M. Wooldridge. How to Rig Elections and Competitions. COMSOC 2008.</li>
<li>Thuc Vu, Alon Altman, Yoav Shoham. On the complexity of schedule control problems for knockout tournaments. AAMAS (1) 2009: 225-232.</li>
<li>V. Vassilevska Williams. Fixing a tournament. AAAI 2010.</li>
</ol>

CC BY-SA 2.5
2010-08-24T01:07:19.820Z
2010-08-24T05:27:22.730Z
2010-08-24T05:27:22.730Z
virgi
<p>A graph $G = (V,E)$ is said to be labeled by $f$ if each vertex $v\in V$ is assigned a non-negative integer value $f(v)$ and each edge $e = uv\in E$ is assigned the value $|f(u) − f(v)|$. The labeling is graceful if $f : V\rightarrow \{0, 1, 2,\dots, |E|\}$ is an injection and if all edges of G have distinct labels from $\{1, 2,..., |E|\}$. A graph is said to be graceful if it admits a graceful labeling. The computational complexity of deciding whether a graph is graceful is not known.</p>

<ol>
<li>J.A. Gallian. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, 2009. </li>
<li>D.S. Johnson. The NP-completeness column: An ongoing guide. J. Algorithms, 4(1):87–100, 1983.</li>
<li>D.S. Johnson. The NP-completeness column. ACM Transactions on Algorithms, 1(1):160–176, 2005.</li>
</ol>

CC BY-SA 3.0
2011-05-03T18:14:13.643Z
2011-05-03T18:14:13.643Z
Oleksandr Bondarenko
<p>The problem of finding <a href="http://www.sciencedirect.com/science/article/pii/S0022000096900586">Vapnik–Chervonenkis dimension</a> is not known to be in $P$ neither known to be $NP$-complete. The problem can be solved by quasi-polynomial time algorithm ($ O(n^{\log n})$). The problem can not be $NP$-complete unless $NP$ is contained in Quasi-polynomial time.</p>

CC BY-SA 3.0
2013-11-21T17:58:54.500Z
I think it's worth mentioning the classes $\mathsf{LOGNP}$ and $\mathsf{NP}[\log^2 n]$ defined in the paper linked in the answer as well as the other natural problems in that paper that are shown to be in these classes, since any problem complete for these classes is likely to be of intermediate complexity.
Joshua Grochow
CC BY-SA 3.0
2013-11-21T10:37:32.373Z
2013-11-21T10:37:32.373Z
Mohammad Al-Turkistany
<p>In the <a href="http://books.google.com/books?id=JogZAQAAIAAJ&amp;q=%22linear+divisibility%22&amp;dq=%22linear+divisibility%22&amp;hl=en&amp;ei=_EwxTe2rMsaSOsru9LQC&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=23&amp;ved=0CIUBEOgBMBY" rel="noreferrer">linear divisibility</a> problem, the input is two integers $a$ and $b$ and the task is to determine whether there exists an integer of the form $a \cdot x+1$ that divides $b$.</p>

<p>The linear divisibility problem is known to be $\gamma$-complete for NP but not known (AFAIK) to be NP-complete.</p>

<p>Garey and Johnson in their seminal "Computers and Intractability" say that (pp. 158-159):</p>

<blockquote>
  <p>A $\gamma$-reduction, in contrast to our other notions of reducibility, is nondeterministic in nature. Let us first introduce the notion of the relation $R_M$ computed by an NDTM program $M$:$$R_M=\{\langle x,y\rangle:there\ is\ a\ string\ z\ such\ that\ on\ input\ x\ and\ guess\ z\ M\ has\ output\ y\}$$
  (where the definition of "output" is as in the computation of functions by DTMs).</p>
  
  <p>We say that a language $L_1$ over alphabet $\Sigma_1$ is $\gamma$-reducible to a language $L_2$ over $\Sigma_2$ (written $L_1\propto_{\gamma}L_2$) if there is a polynomial time NDTM program $M$ such that for all $x\in\Sigma_1^*$ there is some $y\in\Sigma_2^*$ for which $\langle x,y\rangle\in R_M$ and such that for all $\langle x,y\rangle\in R_M$, $x\in L_1$ if and only if $y\in L_2$. In other words, there is at least one halting computation for $M$ on every input $x$ and, given an input $x$, all halting computations on $x$ yield outputs that are in $L_2$ if and only if $x\in L_1$. </p>
</blockquote>

CC BY-SA 3.0
2011-08-12T13:41:03.110Z
Can you define $\gamma$-completeness in your answer?
Lev Reyzin
CC BY-SA 3.0
2011-01-15T07:32:52.953Z
2011-08-20T14:42:27.383Z
2011-08-20T14:42:27.383Z
Oleksandr Bondarenko
<p>The cutting stock problem with a constant number of object lengths. <a href="https://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827">See this discussion</a> for more information. </p>

CC BY-SA 2.5
2010-12-17T16:33:56.163Z
2010-12-17T16:33:56.163Z
2017-04-13T12:32:28.117Z
Suresh Venkat
<p>The gap version of the closest vector in lattice problem is the following: Given a basis for an $n$-dimensional lattice and a vector $v$, distinguish between the two cases where there is a lattice vector at distance at most one $1$ from $v$ or when every lattice vector is $\beta$-far from $v$, for some fixed gap parameter $\beta &gt; 1$.</p>

<p>When $\beta = \sqrt{n}$, the problem is in $\mathsf{NP} \cap \mathsf{coNP}$ and thus unlikely to be $\mathsf{NP}$-complete (and is conjectured to be outside $\mathsf{P}$). This case is of central attention for lattice-based cryptography and the related dihedral hidden subgroup problem in quentum computing. When $\beta$ is much smaller, say $\beta = n^{o(1/\log \log n)}$, the problem becomes $\mathsf{NP}$-hard.</p>

CC BY-SA 3.0
2011-08-17T20:08:18.653Z
2011-08-17T20:08:18.653Z
Mahdi Cheraghchi
<p>The problem of finding a <a href="http://www.sciencedirect.com/science/article/pii/0304397588901314" rel="noreferrer">minimum dominating set in tournament</a> is not known to be in $P$ neither known to be $NP$-complete. The problem has quasi-polynomial time algorithm ($ O(n^{\log n})$). If the problem has polynomial time algorithm then satisfiability can be solved in sub-exponential time.  </p>

CC BY-SA 3.0
2013-11-21T09:57:16.767Z
2013-11-21T09:57:16.767Z
Mohammad Al-Turkistany
<p>The following problem is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.</p>

<p><strong>Exponentiating Polynomial Root Problem (EPRP)</strong></p>

<p>Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of:
$$p(x) = r^x $$
(or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.</p>

<p>Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate as well.</p>

<p>For additional details see <a href="https://cstheory.stackexchange.com/questions/20609/complexity-class-of-this-problem">my question and related discussion</a>.</p>

CC BY-SA 3.0
2014-03-05T17:04:01.450Z
2014-03-05T17:04:01.450Z
2017-04-13T12:32:28.077Z
Massimo Cafaro
<p>I don't know whether the weighted hypergraph isomorphism problem proposed in the answer by Thinh D. Nguyen cannot be simply shown to be GI complete. However, there is a GI-hard problem closely related to GI, which has not been reduced to GI yet, namely the string isomorphism problem (also called <a href="https://arxiv.org/abs/1609.08253" rel="noreferrer">color isomorphism problem</a>). This is the problem actually shown to be in quasi-polynomial time by László Babai. It is of independent interest, since it is equivalent to a number of decision problems in (permutation) group theory:</p>

<ul>
<li><a href="https://groupprops.subwiki.org/wiki/Coset_intersection_problem" rel="noreferrer">coset intersection problem</a></li>
<li><a href="https://groupprops.subwiki.org/wiki/Double_coset_membership_testing_problem" rel="noreferrer">double coset membership testing problem</a></li>
<li><a href="https://groupprops.subwiki.org/wiki/Group_factorization_problem" rel="noreferrer">group factorization problem</a></li>
</ul>

CC BY-SA 4.0
2020-08-16T16:34:44.910Z
Indeed, weighted hypergraph iso is GI-complete.
Joshua Grochow
CC BY-SA 4.0
2018-06-08T07:42:17.133Z
2018-06-08T07:42:17.133Z
Thomas Klimpel
<p>A problem that is not known to be either in FP or to be NP-hard is the problem of finding a minimal Steiner tree when the Steiner vertices are promised to fall on two straight line segments intersecting at an angle of 120°.
If the angle between the line segments is less than 120°, then the problem is NP-hard.
It is conjectured that when the angle is greater than 120°, then the problem is in FP.</p>

<p>Hence the following decision problem currently appears to be of intermediate complexity:</p>

<blockquote>
  <p><strong>Minimal 120°-Steiner tree</strong><br>
  <em>Input:</em> a finite set of points in the plane, lying on two line segments intersecting at an angle of 120°, and a positive rational number $q$.<br>
  <em>Question:</em> is there a Steiner tree of total length at most $q$?</p>
</blockquote>

<p>Of course, this may actually be in P or be NP-complete, but then it seems we would have an interesting dichotomy at 120° instead of an intermediate problem.
(The conjecture may also be false.)</p>

<ul>
<li>J. H. Rubinstein, D. A. Thomas, N. C. Wormald, <em>Steiner Trees for Terminals Constrained to Curves</em>, SIAM J. Discrete Math. <strong>10</strong>(1) 1–17, 1997.
doi:<a href="http://dx.doi.org/10.1137/S0895480192241190" rel="nofollow">10.1137/S0895480192241190</a></li>
</ul>

CC BY-SA 3.0
2015-08-03T10:17:01.473Z
2015-08-03T10:17:01.473Z
András Salamon
<p>The <a href="https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm" rel="nofollow noreferrer">Coffman–Graham algorithm</a> solves scheduling N jobs (with unit length and DAG dependency) on K=2 machines with minimal span in polynomial time. When K is not a constant, the problem is known to be NPC. However, when K is a constant like 3, the problem is not known to be in P or NPC.</p>

CC BY-SA 4.0
2022-04-05T21:36:50.610Z
2022-04-05T21:36:50.610Z
Peng Du
<p>A handful of natural problems are (promise) <span class="math-container">$\mathsf{BQP\:complete}$</span>, and thus are not likely to be <span class="math-container">$\mathsf{NP\:complete}$</span> under the reasonable hypothesis that <span class="math-container">$\mathsf{NP}\not\subseteq\mathsf{BQP}$</span>.</p>
<p>Adjusting the hypotheses to remove negative signs might negate the strength provided by interference, landing the problem in <span class="math-container">$\mathsf{NP}$</span> and not empowering it to be <span class="math-container">$\mathsf{BQP\:complete}$</span>.</p>
<p>For example estimating an entry <span class="math-container">$(A^m)_{ij}$</span> of the <span class="math-container">$m^{th}$</span> power of a large, sparse matrix <span class="math-container">$A$</span> with <span class="math-container">$\mathcal{O}(\exp m)$</span> entries <span class="math-container">$A_{ij}\in\{-1,0,1\}$</span> is <span class="math-container">$\mathsf{BQP\: complete}$</span>, as shown <a href="https://theoryofcomputing.org/articles/v003a004/v003a004.pdf" rel="nofollow noreferrer">here</a>.</p>
<p><em>I believe</em> that when the entries <span class="math-container">$A_{ij}\in\{0,1\}$</span>, e.g. when <span class="math-container">$A$</span> is an adjacency matrix of a large graph and <span class="math-container">$(A^m)_{ij}$</span> counts the number of <span class="math-container">$m$</span>-length walks from vertex <span class="math-container">$i$</span> to vertex <span class="math-container">$j$</span>, the estimation is amenable to Stockmeyer approximation, and thus likely in <span class="math-container">$\mathsf{AM}$</span>, but still not <span class="math-container">$\mathsf{NP\:complete}$</span>.</p>

CC BY-SA 4.0
2020-08-16T02:03:46.427Z
Is the 01-version of this problem even in NP?
Joshua Grochow
CC BY-SA 4.0
2020-08-16T02:17:47.707Z
I don’t know! If Stockmeyer counting works then it is maybe in AM... which by a reasonable assumption is equal to NP. But I don’t know if there’s another path to NP.  (The BQP algorithm has a lot of similarities to the HHL algorithm. It might even be in P if it could be dequantized as part of the program initiated by Tang, but on that I’m doubtful.)
Mark S
CC BY-SA 4.0
2020-08-15T23:11:50.980Z
2020-08-15T23:45:55.107Z
2020-08-15T23:45:55.107Z
Mark S
<p>Here's a collection of some of the responses of problems between P and NPC:</p>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Integer_factorization" rel="noreferrer">Factoring</a></li>
<li>Isomorphism problems: Graph Isomorphism [not NPC unless <span class="math-container">$\sum_2^p=\prod_2^p$</span>] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, <a href="http://dimacs.rutgers.edu/%7Ekayaln/pdf/ringAuto_journal.pdf" rel="noreferrer">Ring Isomorphism and Automorphism</a> (via @Joshua Grochow)</li>
<li><a href="http://portal.acm.org/citation.cfm?id=12143" rel="noreferrer">Computing the rotation distance</a> between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)</li>
<li><a href="http://portal.acm.org/citation.cfm?id=98598&amp;dl=GUIDE," rel="noreferrer">The Turnpike Problem</a> of reconstructing points on line from distances (via @Suresh Venkat)</li>
<li>Problems arising from the <a href="http://en.wikipedia.org/wiki/Unique_games_conjecture" rel="noreferrer">Unique Games Conjecture</a> (via @Moritz)</li>
<li><a href="http://www.rsa.com/rsalabs/node.asp?id=2193" rel="noreferrer">Discrete Log Problem</a> and others related to cryptographic assumptions (via @Joe Fitzsimons)</li>
<li>Determining winner in <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/" rel="noreferrer">parity games</a> (via @mashca)</li>
<li>Determining who has the highest chance of winning a <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/" rel="noreferrer">stochastic game</a> (via @Peter Shor on MO)</li>
<li><a href="http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html" rel="noreferrer">Numbers in boxes</a> problems (via @Joshua Grochow)</li>
<li><a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460">Agenda control for balanced single-elimination tournaments</a> (via @virgi)</li>
<li><a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106">Knot triviality</a> (via @JeffE)</li>
<li>(Assuming NEXP≠EXP) padded versions of <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:N#nexp" rel="noreferrer">NEXP</a>-complete problems (via @Joshua Grochow)</li>
<li>Problems in <a href="http://theory.stanford.edu/%7Emegiddo/pdf/papadimX.pdf" rel="noreferrer">TFNP</a> (via @Marcos Villagra)</li>
<li><a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739">Intersecting Monotone SAT</a> (via @András Salamon)</li>
<li><a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745">Minimum Circuit Size Problem</a> (via @Eric Allender)</li>
<li>Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)</li>
<li>The <a href="https://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827">Cutting Stock Problem</a> with a constant number of object lengths (via @Suresh Venkat)</li>
<li><a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950">Monotone Self-Duality</a> (via @Danu)</li>
<li><a href="http://portal.acm.org/citation.cfm?id=668338" rel="noreferrer">Planar Minimum Bisection</a> (via @turkistany)</li>
<li><a href="http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality" rel="noreferrer">Pigeonhole Subset Sum</a> (via @user834)</li>
<li><a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010">Square Root Sums</a> (via @JeffE)</li>
<li>Deciding Whether a Graph Admits a <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384">Graceful Labeling</a> (via @Oleksandr Bondarenko)</li>
<li>Gap version of the <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806">closest vector in lattice</a> problem GapCVP<span class="math-container">$(\sqrt{n})$</span> (via @MCH)</li>
<li>The <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331">linear divisibility</a> problem [known to be <span class="math-container">$\gamma$</span>-complete but not NPC] (via @Oleksandr Bondarenko)</li>
<li>Finding the <a href="http://en.wikipedia.org/wiki/VC_dimension" rel="noreferrer">VC dimension</a> (via @Mohammad al Turkistany)</li>
<li>Finding the <a href="http://www.sciencedirect.com/science/article/pii/0304397588901314" rel="noreferrer">minimum dominating set in a tournament</a> (via @Mohammad al Turkistany)</li>
</ul>

CC BY-SA 3.0
2011-06-25T17:57:57.280Z
Are any of these examples *provably* NP-intermediate, assuming only some "reasonable" hypothesis (i.e., a hypothesis less trivial than "this problem is NP-intermediate")?  If so, it would be interesting to mention that in this list.
Timothy Chow
CC BY-SA 3.0
2011-06-27T13:38:30.747Z
@Timothy Chow, that's a good question, and it would be useful information to have in this list. Anyhow who knows should feel free to edit this answer with the relevant details.
Lev Reyzin
CC BY-SA 3.0
2011-06-30T19:59:02.603Z
@Timothy Chow, @Lev Reyzin.  Graph isomorphism is not NP-complete unless $\Sigma_2^p = \Pi_2^p$, because graph non-isomorphism is in AM, and coNP in AM implies $\Sigma_2^p = \Pi_2^p$.  This would work for other problems whose complements are in AM.  This of course does not rule out GI being in P.
Jeff KInne
CC BY-SA 3.0
2011-08-08T22:18:22.920Z
@Lev, maybe you should edit the question to include Timothy's comments since it is less likely that people will see it here.
Kaveh
CC BY-SA 3.0
2011-08-09T20:44:37.173Z
@Timothy Chow: The example above assuming $NEXP \neq EXP$ is provably intermediate, that is, assuming $NEXP \neq EXP$, the padded version of a $NEXP$-complete problem is provably neither $NP$-complete by Mahaney nor in $P$, as that would contradict $NEXP \neq EXP$.
Joshua Grochow
CC BY-SA 4.0
2020-08-14T14:46:05.287Z
Removed the entry _clustered planarity_, which has been [shown to be in P](https://arxiv.org/abs/1907.13086) recently.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-08-19T02:52:07.920Z
I don't know what the community wiki etiquette is here, but maybe this summary should be added as an addendum to the question statement?
Joshua Grochow
CC BY-SA 2.5
2010-08-19T04:08:53.277Z
I made this the "accepted answer" as it combines all of the answers herein.  Making this answer a part of the question seems strange, but I don't object to doing that... I know it's kinda weird for me to make "my" answer the accepted one. I welcome opinions on whether I should change it.
Lev Reyzin
CC BY-SA 2.5
2010-08-24T09:46:04.787Z
@Lev: This is perfect if you keep the summary updated. Then we can upvote this and it'll stay near the top.
Jukka Suomela
CC BY-SA 2.5
2010-08-24T22:06:27.537Z
@Jukka Sounds good. I'll try to keep the list updated.
Lev Reyzin
CC BY-SA 2.5
2010-09-09T00:06:19.227Z
Yes, this procedure works, as the "official" answer.
Suresh Venkat
CC BY-SA 2.5
2010-09-27T21:33:27.200Z
It would be great to be able to add an answer to one's watchlist.  This would definitely be on mine.
András Salamon
CC BY-SA 2.5
2011-02-24T21:50:20.040Z
I'm removing Planar MAX 2-SAT from the list, it was shown to be NP-complete by Guibas et al. in "Approximating polygons and subdivisions with minimum link paths" (http://www.springerlink.com/content/y234m35416w043v1/)
Bob Fraser
CC BY-SA 4.0
2010-08-18T04:09:07.930Z
2020-08-14T14:44:51.400Z
2020-08-14T14:44:51.400Z
Lev Reyzin
<p>Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete.  What are some other (sufficiently different) natural problems that share this property?  Artificial examples coming directly from the proof of Ladner's theorem do not count.</p>

<p>Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?</p>

CC BY-SA 2.5
2010-08-17T02:13:39.143Z
There is a similar question asked here that may be useful:

http://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np/54#54
Daniel Apon
CC BY-SA 2.5
2010-08-17T02:29:32.100Z
Related question at MO, with several pointers specifically for problems in NP and co-NP but not known to be in P: http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p
András Salamon
CC BY-SA 2.5
2010-08-17T02:36:30.867Z
There are several complexity classes between P and NP-complete which are currently regarded as interesting: PPAD, problems that are UGC-equivalent, NP $\cap$ co-NP, BPP,....  If you are asking for a big list, could you make this a community wiki please?
András Salamon
CC BY-SA 2.5
2010-08-17T03:05:22.043Z
Thank you.  I am aware of Ladner's Theorem.  I guess I was asking for "natural problems."  I guess PPAD has Nash Equilibria, so that counts...
Lev Reyzin
<cc.complexity-theory><np-hardness><big-list><np-intermediate>
Problems Between P and NPC
Lev Reyzin
# Problems Between P and NPC

(Asked by: username_0 on 2010-08-17)

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? Artificial examples coming directly from the proof of Ladner's theorem do not count.

Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?

**Tags:** cc.complexity-theory, np-hardness, big-list, np-intermediate
> **Comments:**
> **username_1**: There is a similar question asked here that may be useful:  http://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np/54#54  
> **username_2**: Related question at MO, with several pointers specifically for problems in NP and co-NP but not known to be in P: http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p  
> **username_2**: There are several complexity classes between P and NP-complete which are currently regarded as interesting: PPAD, problems that are UGC-equivalent, NP $\cap$ co-NP, BPP,....  If you are asking for a big list, could you make this a community wiki please?  
> **username_0**: Thank you.  I am aware of Ladner's Theorem.  I guess I was asking for "natural problems."  I guess PPAD has Nash Equilibria, so that counts...  

---

## 29 answers

### Answer by username_0 on 2010-08-18. Score: 116 | Accepted answer

Here's a collection of some of the responses of problems between P and NPC:

* [Factoring](http://en.wikipedia.org/wiki/Integer_factorization)
* Isomorphism problems: Graph Isomorphism [not NPC unless $\sum\_2^p=\prod\_2^p$] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, [Ring Isomorphism and Automorphism](http://dimacs.rutgers.edu/%7Ekayaln/pdf/ringAuto_journal.pdf) (via @Joshua Grochow)
* [Computing the rotation distance](http://portal.acm.org/citation.cfm?id=12143) between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)
* [The Turnpike Problem](http://portal.acm.org/citation.cfm?id=98598&dl=GUIDE,) of reconstructing points on line from distances (via @Suresh Venkat)
* Problems arising from the [Unique Games Conjecture](http://en.wikipedia.org/wiki/Unique_games_conjecture) (via @Moritz)
* [Discrete Log Problem](http://www.rsa.com/rsalabs/node.asp?id=2193) and others related to cryptographic assumptions (via @Joe Fitzsimons)
* Determining winner in [parity games](http://kintali.wordpress.com/2010/06/06/np-intersect-conp/) (via @mashca)
* Determining who has the highest chance of winning a [stochastic game](http://kintali.wordpress.com/2010/06/06/np-intersect-conp/) (via @Peter Shor on MO)
* [Numbers in boxes](http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html) problems (via @Joshua Grochow)
* [Agenda control for balanced single-elimination tournaments](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460) (via @virgi)
* [Knot triviality](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106) (via @JeffE)
* (Assuming NEXP≠EXP) padded versions of [NEXP](http://qwiki.stanford.edu/wiki/Complexity_Zoo:N#nexp)-complete problems (via @Joshua Grochow)
* Problems in [TFNP](http://theory.stanford.edu/%7Emegiddo/pdf/papadimX.pdf) (via @Marcos Villagra)
* [Intersecting Monotone SAT](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739) (via @András Salamon)
* [Minimum Circuit Size Problem](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745) (via @Eric Allender)
* Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)
* The [Cutting Stock Problem](https://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827) with a constant number of object lengths (via @Suresh Venkat)
* [Monotone Self-Duality](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950) (via @Danu)
* [Planar Minimum Bisection](http://portal.acm.org/citation.cfm?id=668338) (via @turkistany)
* [Pigeonhole Subset Sum](http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality) (via @user834)
* [Square Root Sums](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010) (via @JeffE)
* Deciding Whether a Graph Admits a [Graceful Labeling](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384) (via @Oleksandr Bondarenko)
* Gap version of the [closest vector in lattice](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806) problem GapCVP$(\sqrt{n})$ (via @MCH)
* The [linear divisibility](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331) problem [known to be $\gamma$-complete but not NPC] (via @Oleksandr Bondarenko)
* Finding the [VC dimension](http://en.wikipedia.org/wiki/VC_dimension) (via @Mohammad al Turkistany)
* Finding the [minimum dominating set in a tournament](http://www.sciencedirect.com/science/article/pii/0304397588901314) (via @Mohammad al Turkistany)

> **Comments:**
> **username_10**: I don't know what the community wiki etiquette is here, but maybe this summary should be added as an addendum to the question statement?  
> **username_0**: I made this the "accepted answer" as it combines all of the answers herein.  Making this answer a part of the question seems strange, but I don't object to doing that... I know it's kinda weird for me to make "my" answer the accepted one. I welcome opinions on whether I should change it.  
> **username_33**: @Lev: This is perfect if you keep the summary updated. Then we can upvote this and it'll stay near the top.  
> **username_0**: @Jukka Sounds good. I'll try to keep the list updated.  
> **username_9**: Yes, this procedure works, as the "official" answer.  
> **username_2**: It would be great to be able to add an answer to one's watchlist.  This would definitely be on mine.  
> **username_34**: I'm removing Planar MAX 2-SAT from the list, it was shown to be NP-complete by Guibas et al. in "Approximating polygons and subdivisions with minimum link paths" (http://www.springerlink.com/content/y234m35416w043v1/)  
> **username_29**: Are any of these examples *provably* NP-intermediate, assuming only some "reasonable" hypothesis (i.e., a hypothesis less trivial than "this problem is NP-intermediate")?  If so, it would be interesting to mention that in this list.  
> **username_0**: @Timothy Chow, that's a good question, and it would be useful information to have in this list. Anyhow who knows should feel free to edit this answer with the relevant details.  
> **username_30**: @Timothy Chow, @Lev Reyzin.  Graph isomorphism is not NP-complete unless $\Sigma_2^p = \Pi_2^p$, because graph non-isomorphism is in AM, and coNP in AM implies $\Sigma_2^p = \Pi_2^p$.  This would work for other problems whose complements are in AM.  This of course does not rule out GI being in P.  
> **username_31**: @Lev, maybe you should edit the question to include Timothy's comments since it is less likely that people will see it here.  
> **username_10**: @Timothy Chow: The example above assuming $NEXP \neq EXP$ is provably intermediate, that is, assuming $NEXP \neq EXP$, the padded version of a $NEXP$-complete problem is provably neither $NP$-complete by Mahaney nor in $P$, as that would contradict $NEXP \neq EXP$.  
> **username_32**: Removed the entry _clustered planarity_, which has been [shown to be in P](https://arxiv.org/abs/1907.13086) recently.  

---

### Answer by username_3 on 2010-12-29. Score: 47

**The sums of square roots problem:** Given two sequences $a\_1, a\_2, \dots, a\_n$ and $b\_1, b\_2, \dots, b\_n$ of positive integers, is $A := \sum\_i \sqrt{a\_i}$ less than, equal to, or greater than $B := \sum\_i \sqrt{b\_i}$?

* The problem has a trivial $O(n)$-time algorithm on the real RAM—Just compute the sums and compare them!—but this does not imply membership in P.
* There is an obvious finite-precision algorithm, but it is not known whether a polynomial number of bits of precision is sufficient for correctness. (See <https://topp.openproblem.net/p33> for details.)
* The Pythogorean theorem implies that the length of any polygonal curve whose vertices and integer endpoints is a sum of square roots of integers. Thus, the sum-of-roots problem is inherent in several planar computational geometry problems, including [Euclidean minimum spanning trees](http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree), [Euclidean shortest paths](http://en.wikipedia.org/wiki/Euclidean_shortest_path), [minimum-weight triangulations](http://en.wikipedia.org/wiki/Minimum-weight_triangulation), and the [Euclidean traveling salesman problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem#With_metric_distances). (The Euclidean MST problem can be solved in polynomial time without resolving the sum-of-roots problem, thanks to the underlying matroid structure and the fact that the EMST is a subgraph of the Delaunay triangulation.)
* There *is* a polynomial-time randomized algorithm, [due to Johannes Blömer](http://doi.ieeecomputersociety.org/10.1109/SFCS.1991.185434), to decide whether the two sums are equal. However, if the answer is no, Blömer's algorithm does not determine which sum is larger.
* The decision version of this problem (Is $A > B$?) is not even known to be in NP. However, Blömer's algorithm implies that if the decision problem is in NP, then it is also in co-NP. Thus, the problem is unlikely to be NP-complete.

> **Comments:**
> **username_4**: Well, if we take just 1000 random integers, not too large, then there are about $2^{999}$ ways to divide them into two sets, so I would expect that two of these sums are within 900 or more bits within each other (and within half of the total sum). On the other hand, finding the "worst" two sequences to compare out of these $2^{999}$ possibilities is also very, very hard.  
> **username_5**: The question asks for a problem in NP, but this answer says the problem is not known to be in NP?  

---

### Answer by username_6 on 2010-08-17. Score: 46

My favorite problem in this class (I'll phrase it as a functional problem, but it's easy to turn into a decision problem in the standard way): compute the rotation distance between two binary trees (equivalently, the flip distance between two triangulations of a convex polygon).

> **Comments:**
> **username_9**: That's a neat problem: I didn't realize it was in limbo.  
> **username_0**: Yeah I didn't know about it either! For all these problems/answers, I wonder if  they are in Limbo because we think they really are or if they're more like PRIMES...  
> **username_10**: This problem and its potentially intermediate status should be more well-known.  Can you give a reference to it?  Also, is there any result indicating that it is not NP-complete, as there is for Graph Isomorphism and related problems?  
> **username_6**: A very pretty and important but older reference is Thurston, Sleator, and Tarjan, "Rotation distance, triangulations, and hyperbolic geometry", STOC'86 and JAMS'88. For a recent reference that explicitly mentions the complexity of the problem as still being open, see Lucas, "An improved kernel size for rotation distance in binary trees", IPL 2010, http://dx.doi.org/10.1016/j.ipl.2010.04.022  
> **username_8**: Interesting. Exploring the rotation space is also an active area of research it seems. "The rotation graph of k-ary trees is Hamiltonian", IPL 2008, http://dx.doi.org/10.1016/j.ipl.2008.09.013  
> **username_7**: See also "*A Note on the Flip Distance Problem for Edge-Labeled Triangulations*" ([Arxiv, 2018](https://arxiv.org/abs/1808.03126)).  

---

### Answer by username_9 on 2010-08-17. Score: 40

A problem that is mentioned neither in this list or the MO list is the turnpike problem. Given a multiset of n(n-1)/2 numbers, each number representing the distance between two points on the line, reconstruct the positions of the original points.

Note that what makes this nontrivial is that for a given number d in the multiset, you don't know which pair of points is d units apart.

[While it is known](http://portal.acm.org/citation.cfm?id=98598&dl=GUIDE,) that for any given instance there are only a polynomial number of solutions, it is not known how to find one !

> **Comments:**
> **username_0**: Thanks - this is a good one!  Reminds me of some other "localization" problems.  Is it actually thought to be not in p?  
> **username_9**: I am not aware that turnpike is directly linked to known problems in complexity. However, there's a "wrong direction" relation to factoring, in that the turnpike problem cam be phrased as a factoring problem on an appropriately chosen polynomial.  
> **username_10**: Are there known unlikely consequences of this problem being NP-complete, as there are for Graph Isomorphism (PH collapsing)?  
> **username_9**: not that I'm aware of. it hasn't been studied that much, which is a pity, because it's so natural.  
> **username_12**: You encounter a similar problem in bioinformatics: Given a set of potentially/hopefully overlapping, randomly created substrings of a string much longer than the individual pieces; compute the original string. (gene sequencing)  
> **username_11**: @SureshVenkat this is awesome, reminds me of [Golomb Rulers](https://en.wikipedia.org/wiki/Golomb_ruler).  What is the "factoring" problem to which you refer? Are the coefficients of the polynomial in $x^i$ the multiset values at $i$? Would this, then, be amenable to [Shor's](https://en.wikipedia.org/wiki/Shor%27s_algorithm) algorithm on a quantum computer?  

---

### Answer by username_10 on 2010-08-17. Score: 30

Here is a list of problems that may or may not qualify as "sufficiently" different. By the same proof as for Graph Isomorphism, if any of them is NP-complete, then the Polynomial Hierarchy collapses to the second level. I do not think there is any broad consensus as to which of these "ought" to be in P.

* Graph Automorphism (determine if a graph has a nontrivial automorphism). Reduces to Graph Isomorphism, but not known (not thought?) to be GI-hard.
* Group Isomorphism and Automorphism (where the groups are given by their multiplication tables). Again, reduces to Graph Isomorphism, but not thought to be GI-hard.
* Ring Isomorphism and Automorphism. In a sense, this is the grand-daddy of all the above problems, since integer factoring is equivalent to finding a nontrivial automorphism of a ring, and Graph Isomorphism reduces to Ring Isomorphism. See [Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems.
  Computational Complexity 15(4): 342-390 (2006).](http://dimacs.rutgers.edu/~kayaln/pdf/ringAuto_journal.pdf) (Interestingly, *determining* if a ring has a nontrivial automorphism is in $P$.)
* [This post](http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html) by Bill Gasarch contains some other problems with the taste of Ramsey theory that look like they might be intermediate.
* By Mahaney's Theorem, no sparse set can be NP-complete. But we also know that there are sparse sets in $NP$ - $P$ iff $NEXP$ is not equal to $EXP$. So assuming $NEXP \neq EXP$, the padded version of any $NEXP$-complete problem is of intermediate complexity. (Such a set cannot be in $P$ unless $NEXP = EXP$, contradicting our assumption.) There are plenty of natural $NEXP$-complete problems.

> **Comments:**
> **username_13**: I like the last example. Do you have any references about it?  
> **username_10**: S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.  http://dx.doi.org/10.1016/0022-0000(82)90002-2  Sparse sets in NP - P iff NEXP neq EXP:   J. Hartmanis, N. Immerman, V. Sewelson, Sparse sets in NP-P: EXPTIME versus NEXPTIME, Information and Control, Volume 65, Issues 2-3, May-June 1985, Pages 158-181.  http://dx.doi.org/10.1016/S0019-9958(85)80004-8  
> **username_0**: This is a nice list, though the first three are quite similar :)  I like the last example as well.  

---

### Answer by username_14 on 2010-09-28. Score: 30

The Minimum Circuit Size Problem (MCSP) is my favorite "natural" problem in NP that's not known to be NP-complete: Given the truth-table (of size n=2^m) of an m-variate Boolean function f, and given a number s, does f have a circuit of size s? If MCSP is easy, then there is no cryptographically-secure one-way function. This problem and its variants provided much of the motivation for the study of "brute-force" algorithms in Russia, leading to Levin's work on NP-completeness. This problem can also be viewed in terms of resource-bounded Kolmogorov complexity: asking if a string can be recovered quickly from a short description. This version of the problem was studied by Ko; the name MCSP was used first by Cai and Kabanets, as far as I know. More references can be found in some papers of mine:
<http://ftp.cs.rutgers.edu/pub/allender/KT.pdf>
http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf


---

### Answer by username_15 on 2010-12-23. Score: 24

**Monotone self-duality**

For any boolean function $f=f(x\_1, x\_2, ..., x\_n)$, it's dual is $f^d=\bar{f}(\bar{x\_1}, \bar{x\_2}, ..., \bar{x\_n})$. Given $f(x\_1, x\_2, ..., x\_n)$ represented by a CNF formula, we have to decide whether $f=f^d$.

This problem is in co-NP[$\log^2 n$], i.e., it is decidable with $O(\log^2n/ \log\log n)$ nondeterministic steps. Thus, it has a quasi-polynomial time algorithm ($O(n^{\log n/\log \log n})$ time), and hence is unlikely to be co-NP-hard.

It is still open whether this problem is in P or not. More details can be found in the 2008 paper "[Computational aspects of monotone dualization: A brief survey](http://dx.doi.org/10.1016/j.dam.2007.04.017)" by Thomas Eiter, Kazuhisa Makino, and Georg Gottlob.


---

### Answer by username_3 on 2010-09-09. Score: 23

Knot triviality: Given a closed polygonal chain in 3-space, is it unknotted (ie, ambient-isotopic to a flat circle)?

This is known to be in NP by deepish results in normal surface theory, but no poly-time algorithm or NP-hardness proof is known.

> **Comments:**
> **username_10**: It might be worth mentioning that, as with many potentially NP-intermediate problems, a slight variant is known to be NP-complete. Namely, 3-manifold knot genus is NP-complete: given a closed polygonal chain in a triangulated 3-manifold and an integer g, is the knot the boundary of a surface of genus at most g? (Being the unknot is equivalent to genus 0.) http://doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016  
> **username_16**: It's also contained in co-AM (Hara, Tani, Yamamoto), so not NPC unless the polynomial hierarchy collapses.  
> **username_3**: Actually, that's still open.  Tasos Sidiropoulos found a bug in the Hara-Tani-Yamamoto proof.  
> **username_11**: Since the time this answer was first posted, Kuperberg [placed](https://arxiv.org/abs/1112.0845) it in $\mathsf{coNP}$ conditional on the Generalized Riemann Hypothesis, and Lackenby [placed](https://arxiv.org/abs/1302.0180) it unconditonally in $\mathsf{coNP}$.  

---

### Answer by username_2 on 2010-09-27. Score: 19

In a *monotone* CNF formula every clause contains only positive literals or only negative literals. In an *intersecting* monotone CNF formula every positive clause has some variable in common with every negative clause.

The decision problem

> **INTERSECTING MONOTONE SAT**  
> *Input:* intersecting monotone CNF formula $f$  
> *Question:* is $f$ satisfiable?

has an $n^{o(\log\ n)}$ algorithm dating back to 1996, but is not known to be in P. (Of course, it might turn out to be in P, but that would be a major result.)

* Thomas Eiter and Georg Gottlob, *Hypergraph Transversal Computation and Related Problems in Logic and AI*, JELIA 2002. doi: [10.1007/3-540-45757-7\_53](http://10.1007/3-540-45757-7_53)


---

### Answer by username_17 on 2010-08-17. Score: 19

It is not known if it is possible to decide in polynomial time if player 1 has a winning strategy in a parity game (from a given starting position). The problem is, however, contained in NP and co-NP and even in UP and co-UP.

> **Comments:**
> **username_10**: Can you give a reference?  Sounds interesting.  
> **username_17**: M. Jurdzinski. Deciding the Winner in Parity Games is in UP \cap co-Up. Information Processing Letters 68(3):119-124. 1998. Should at least be a good starting point.  
> **username_15**: The recent paper "A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information" also shows that even a generalization of the parity game can be solved in pseudo-polynomial time. In particular, they show that a game called BWR game has a pseudo-polynomial time algorithm when there is a constant number of "random nodes". The parity game is the case where there is no random nodes.  
> **username_18**: It was shown recently that parity games can be solved in quasipolynomial time, see [here](http://cs.stackexchange.com/questions/16399/is-it-possible-to-solve-parity-game-problem-in-polynomial-time/71442#71442) for example.  

---

### Answer by username_19 on 2010-12-28. Score: 18

[The Pigeonhole Version of Subset Sum](http://garden.irmacs.sfu.ca/?q=op/theoretical_computer_science/subset_sums_equality) (or Subset Sum Equality).

Given:

$$a\_k \in \mathbb{Z}\_{>0}$$
$$\sum\_{k=0}^{n-1} a\_k < 2^n - 1$$

By the pigeonhole principle, there must exist two disjoint subsets, $S\_1, S\_2 \subseteq \{ 1, \dots, n \} $ such that:

$$\sum\_{j \in S\_1} a\_j = \sum\_{k \in S\_2} a\_k $$

The pigeonhole subset sum problem asks for such a solution. Originally stated in "[Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.1192&rep=rep1&type=pdf)" by Bazgan, Santha and Tuza.


---

### Answer by username_20 on 2010-08-17. Score: 18

You get a very long list of problems if willing to accept approximation problems, such as approximating Max-Cut to within a factor 0.878. We don't know if it's NP-hard or in P (only know NP-hardness assuming the Uniuqe Games Conjecture).

> **Comments:**
> **username_1**: Yes, that was a silly comment that I started to delete as soon as it was posted. Thank you. :)  
> **username_0**: Thanks! But I guess I wasn't thinking as much about approximation problems, but more of natural problems.  
> **username_20**: Arguably, these are natural problems since they correspond to what is achievable by a natural set of techniques, in this case, semidefinite programming.  
> **username_0**: I guess "natural" is a vague criterion...  

---

### Answer by username_16 on 2010-10-26. Score: 17

Is a given triangulated 3-manifold a 3-sphere? [From Joe O'Rourke.](https://cstheory.stackexchange.com/questions/2429/is-the-3-sphere-recognition-problem-np-complete)


---

### Answer by username_21 on 2010-08-17. Score: 16

There are a lot of problems related to finding hidden subgroups. You mentioned factoring, but there is also the discrete log problem as well as others related to elliptic curves, etc.


---

### Answer by username_24 on 2010-08-24. Score: 15

Here's a problem in computational social choice which is not known to be in P, and may or may not be NP-complete.

Agenda control for balanced single-elimination tournaments:

Given: tournament graph $T$ on $n=2^k$ nodes, node $a$

Question: does there exist a permutation of the nodes (a *bracket*) so that a is the winner of the induced single-elimination tournament?

Given a permutation $P\_k$ on $2^k$ nodes of $V$ and a tournament graph $T$ on $V$, one can obtain a permutation $P\_{k-1}$ on $2^{k-1}$ nodes as follows. For every $i>0$, consider $P\_k[2i-1]$ and $P\_k[2i]$ and the arc $e$ between them in $T$; let $P\_{k-1}[i]=P\_k[2i-1]$ if $e=(P\_k[2i-1],P\_k[2i])$ and $P\_{k-1}[i]=P\_k[2i]$ otherwise.
That is, we match up pairs of nodes according to $P\_k$ and use $T$ to decide which nodes (winners) move on to the next round $P\_{k-1}$. Hence given a permutation on $2^k$ one can actually define $k$ rounds $P\_{k-1},\ldots,P\_0$ inductively as above, until the last permutation contains only one node. This defines a (balanced) single-elimination tournament on $2^k$ nodes. The node which remains after all the rounds is the winner of the tournament.

Agenda control for balanced single-elimination tournaments (graph formulation):

Given: tournament graph $T$ on $n=2^k$ nodes, node $a$

Question: does $T$ contain a (spanning) binomial arborescence on $2^k$ nodes rooted at $a$?

A binomial arborescence on $2^k$ nodes rooted at a node $x$ is defined recursively as $a$ binomial arborescence on $2^{k-1}$ nodes rooted at $x$ and a binomial arborescence on $2^{k-1}$ nodes rooted at a different node $y$ and an arc from $x$ to $y$. (If $k=0$, a binomial arborescence is just the root.) The spanning binomial arborescences in a tournament graph capture exactly the single-elimination tournaments which can be played, given the match outcome information in the tournament graph.

Some references:

1. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: Winner Determination in Sequential Majority Voting. IJCAI 2007: 1372-1377.
2. N. Hazon, P. E. Dunne, S. Kraus, and , M. Wooldridge. How to Rig Elections and Competitions. COMSOC 2008.
3. Thuc Vu, Alon Altman, Yoav Shoham. On the complexity of schedule control problems for knockout tournaments. AAMAS (1) 2009: 225-232.
4. V. Vassilevska Williams. Fixing a tournament. AAAI 2010.


---

### Answer by username_13 on 2010-08-17. Score: 13

Take a look at the class [TFNP](http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf). It has a lot of search problems with an intermediate status.

> **Comments:**
> **username_13**: I should point out that it is the class of related function problems in $NP\cap coNP$.  

---

### Answer by username_22 on 2010-08-17. Score: 12

The induced subgraph isomorphism problem has NP-incomplete "left-hand side restrictions" assuming that P is not equal to NP. See Y. Chen, M. Thurley, M. Weyer: [Understanding the Complexity of Induced Subgraph Isomorphisms](http://dx.doi.org/10.1007/978-3-540-70575-8_48), ICALP 2008.

> **Comments:**
> **username_10**: Although this is an interesting result, if you check the paper it even says that the proof of intermediate complexity is essentially the same as Ladner's Theorem, except you do the diagonalization in the choice of the LHS restriction.  So I don't know if this counts as a "natural" problem, rather than just a different encoding of Ladner's Theorem.  
> **username_2**: Note also that these are source-and-target restrictions.  The target (right hand side) has to be of special form, to enforce injectivity.  

---

### Answer by username_23 on 2010-12-23. Score: 11

The complexity of planar Minimum Bisection problem is an intriguing open problem which is not known to be $NP$-hard. In contrast, the planar Maximum Bisection problem is $NP$-hard.

Minimum Bisection problem: Find a partition of the set of nodes into two equal size parts such that the number of crossing edges is minimized.

[Karpinski, Approximability of the Minimum Bisection Problem: An Algorithmic Challenge](http://portal.acm.org/citation.cfm?id=668338)

> **Comments:**
> **username_0**: do you have a reference to the problem definition?  
> **username_23**: Reference is added.  

---

### Answer by username_9 on 2010-12-17. Score: 10

The cutting stock problem with a constant number of object lengths. [See this discussion](https://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827) for more information.


---

### Answer by username_26 on 2011-08-17. Score: 10

The gap version of the closest vector in lattice problem is the following: Given a basis for an $n$-dimensional lattice and a vector $v$, distinguish between the two cases where there is a lattice vector at distance at most one $1$ from $v$ or when every lattice vector is $\beta$-far from $v$, for some fixed gap parameter $\beta > 1$.

When $\beta = \sqrt{n}$, the problem is in $\mathsf{NP} \cap \mathsf{coNP}$ and thus unlikely to be $\mathsf{NP}$-complete (and is conjectured to be outside $\mathsf{P}$). This case is of central attention for lattice-based cryptography and the related dihedral hidden subgroup problem in quentum computing. When $\beta$ is much smaller, say $\beta = n^{o(1/\log \log n)}$, the problem becomes $\mathsf{NP}$-hard.


---

### Answer by username_25 on 2011-05-03. Score: 9

A graph $G = (V,E)$ is said to be labeled by $f$ if each vertex $v\in V$ is assigned a non-negative integer value $f(v)$ and each edge $e = uv\in E$ is assigned the value $|f(u) − f(v)|$. The labeling is graceful if $f : V\rightarrow \{0, 1, 2,\dots, |E|\}$ is an injection and if all edges of G have distinct labels from $\{1, 2,..., |E|\}$. A graph is said to be graceful if it admits a graceful labeling. The computational complexity of deciding whether a graph is graceful is not known.

1. J.A. Gallian. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, 2009.
2. D.S. Johnson. The NP-completeness column: An ongoing guide. J. Algorithms, 4(1):87–100, 1983.
3. D.S. Johnson. The NP-completeness column. ACM Transactions on Algorithms, 1(1):160–176, 2005.


---

### Answer by username_23 on 2013-11-21. Score: 9

The problem of finding [Vapnik–Chervonenkis dimension](http://www.sciencedirect.com/science/article/pii/S0022000096900586) is not known to be in $P$ neither known to be $NP$-complete. The problem can be solved by quasi-polynomial time algorithm ($ O(n^{\log n})$). The problem can not be $NP$-complete unless $NP$ is contained in Quasi-polynomial time.

> **Comments:**
> **username_10**: I think it's worth mentioning the classes $\mathsf{LOGNP}$ and $\mathsf{NP}[\log^2 n]$ defined in the paper linked in the answer as well as the other natural problems in that paper that are shown to be in these classes, since any problem complete for these classes is likely to be of intermediate complexity.  

---

### Answer by username_25 on 2011-01-15. Score: 8

In the [linear divisibility](http://books.google.com/books?id=JogZAQAAIAAJ&q=%22linear+divisibility%22&dq=%22linear+divisibility%22&hl=en&ei=_EwxTe2rMsaSOsru9LQC&sa=X&oi=book_result&ct=result&resnum=23&ved=0CIUBEOgBMBY) problem, the input is two integers $a$ and $b$ and the task is to determine whether there exists an integer of the form $a \cdot x+1$ that divides $b$.

The linear divisibility problem is known to be $\gamma$-complete for NP but not known (AFAIK) to be NP-complete.

Garey and Johnson in their seminal "Computers and Intractability" say that (pp. 158-159):

> A $\gamma$-reduction, in contrast to our other notions of reducibility, is nondeterministic in nature. Let us first introduce the notion of the relation $R\_M$ computed by an NDTM program $M$:$$R\_M=\{\langle x,y\rangle:there\ is\ a\ string\ z\ such\ that\ on\ input\ x\ and\ guess\ z\ M\ has\ output\ y\}$$
> (where the definition of "output" is as in the computation of functions by DTMs).
>
> We say that a language $L\_1$ over alphabet $\Sigma\_1$ is $\gamma$-reducible to a language $L\_2$ over $\Sigma\_2$ (written $L\_1\propto\_{\gamma}L\_2$) if there is a polynomial time NDTM program $M$ such that for all $x\in\Sigma\_1^\*$ there is some $y\in\Sigma\_2^\*$ for which $\langle x,y\rangle\in R\_M$ and such that for all $\langle x,y\rangle\in R\_M$, $x\in L\_1$ if and only if $y\in L\_2$. In other words, there is at least one halting computation for $M$ on every input $x$ and, given an input $x$, all halting computations on $x$ yield outputs that are in $L\_2$ if and only if $x\in L\_1$.

> **Comments:**
> **username_0**: Can you define $\gamma$-completeness in your answer?  

---

### Answer by username_23 on 2013-11-21. Score: 7

The problem of finding a [minimum dominating set in tournament](http://www.sciencedirect.com/science/article/pii/0304397588901314) is not known to be in $P$ neither known to be $NP$-complete. The problem has quasi-polynomial time algorithm ($ O(n^{\log n})$). If the problem has polynomial time algorithm then satisfiability can be solved in sub-exponential time.


---

### Answer by username_27 on 2014-03-05. Score: 5

The following problem is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.

**Exponentiating Polynomial Root Problem (EPRP)**

Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of:
$$p(x) = r^x $$
(or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.

Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate as well.

For additional details see [my question and related discussion](https://cstheory.stackexchange.com/questions/20609/complexity-class-of-this-problem).


---

### Answer by username_18 on 2018-06-08. Score: 5

I don't know whether the weighted hypergraph isomorphism problem proposed in the answer by Thinh D. Nguyen cannot be simply shown to be GI complete. However, there is a GI-hard problem closely related to GI, which has not been reduced to GI yet, namely the string isomorphism problem (also called [color isomorphism problem](https://arxiv.org/abs/1609.08253)). This is the problem actually shown to be in quasi-polynomial time by László Babai. It is of independent interest, since it is equivalent to a number of decision problems in (permutation) group theory:

* [coset intersection problem](https://groupprops.subwiki.org/wiki/Coset_intersection_problem)
* [double coset membership testing problem](https://groupprops.subwiki.org/wiki/Double_coset_membership_testing_problem)
* [group factorization problem](https://groupprops.subwiki.org/wiki/Group_factorization_problem)

> **Comments:**
> **username_10**: Indeed, weighted hypergraph iso is GI-complete.  

---

### Answer by username_2 on 2015-08-03. Score: 4

A problem that is not known to be either in FP or to be NP-hard is the problem of finding a minimal Steiner tree when the Steiner vertices are promised to fall on two straight line segments intersecting at an angle of 120°.
If the angle between the line segments is less than 120°, then the problem is NP-hard.
It is conjectured that when the angle is greater than 120°, then the problem is in FP.

Hence the following decision problem currently appears to be of intermediate complexity:

> **Minimal 120°-Steiner tree**  
> *Input:* a finite set of points in the plane, lying on two line segments intersecting at an angle of 120°, and a positive rational number $q$.  
> *Question:* is there a Steiner tree of total length at most $q$?

Of course, this may actually be in P or be NP-complete, but then it seems we would have an interesting dichotomy at 120° instead of an intermediate problem.
(The conjecture may also be false.)

* J. H. Rubinstein, D. A. Thomas, N. C. Wormald, *Steiner Trees for Terminals Constrained to Curves*, SIAM J. Discrete Math. **10**(1) 1–17, 1997.
  doi:[10.1137/S0895480192241190](http://dx.doi.org/10.1137/S0895480192241190)


---

### Answer by username_28 on 2022-04-05. Score: 1

The [Coffman–Graham algorithm](https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm) solves scheduling N jobs (with unit length and DAG dependency) on K=2 machines with minimal span in polynomial time. When K is not a constant, the problem is known to be NPC. However, when K is a constant like 3, the problem is not known to be in P or NPC.


---

### Answer by username_11 on 2020-08-15. Score: 1

A handful of natural problems are (promise) $\mathsf{BQP\:complete}$, and thus are not likely to be $\mathsf{NP\:complete}$ under the reasonable hypothesis that $\mathsf{NP}\not\subseteq\mathsf{BQP}$.

Adjusting the hypotheses to remove negative signs might negate the strength provided by interference, landing the problem in $\mathsf{NP}$ and not empowering it to be $\mathsf{BQP\:complete}$.

For example estimating an entry $(A^m)\_{ij}$ of the $m^{th}$ power of a large, sparse matrix $A$ with $\mathcal{O}(\exp m)$ entries $A\_{ij}\in\{-1,0,1\}$ is $\mathsf{BQP\: complete}$, as shown [here](https://theoryofcomputing.org/articles/v003a004/v003a004.pdf).

*I believe* that when the entries $A\_{ij}\in\{0,1\}$, e.g. when $A$ is an adjacency matrix of a large graph and $(A^m)\_{ij}$ counts the number of $m$-length walks from vertex $i$ to vertex $j$, the estimation is amenable to Stockmeyer approximation, and thus likely in $\mathsf{AM}$, but still not $\mathsf{NP\:complete}$.

> **Comments:**
> **username_10**: Is the 01-version of this problem even in NP?  
> **username_11**: I don’t know! If Stockmeyer counting works then it is maybe in AM... which by a reasonable assumption is equal to NP. But I don’t know if there’s another path to NP.  (The BQP algorithm has a lot of similarities to the HHL algorithm. It might even be in P if it could be dequantized as part of the program initiated by Tang, but on that I’m doubtful.)  

---

