<p>Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo."  But besides that, there are several others:</p>

<ul>
<li>Show that your problem is in NP &cap; coNP.  (Example: Factoring.)
<li>Show that your problem is solvable in quasipolynomial time.  (Examples: VC dimension, approximating free games.)
<li>Show that your problem is no harder than inverting one-way functions or solving NP on average.  (Examples: Lots of problems in cryptography.)
<li>Show that your problem reduces to (e.g.) Unique Games or Small-Set Expansion.
<li>Show that your problem is in BQP.  (Example: Factoring, though of course that's also in NP &cap; coNP.)
<li>Rule out large classes of NP-completeness reductions.  (Example: The Circuit Minimization Problem, studied by Kabanets and Cai.)
</ul>

<p>I'm sure there are others that I'm forgetting.</p>

CC BY-SA 3.0
2014-02-06T07:28:06.187Z
That's an excellent list, Scott !
Suresh Venkat
CC BY-SA 3.0
2014-02-08T01:02:14.197Z
Philip: You're right, they don't.  For adducing evidence that a particular NP problem is not in P, it all boils down to (1) trying to put it in P and failing, and/or (2) reducing other problems that people failed to put in P to that problem.
Scott Aaronson
CC BY-SA 3.0
2014-02-05T22:08:09.690Z
2014-02-05T22:08:09.690Z
Scott Aaronson
<p>From the comment above: if a problem seems hard enough, but you are not able to prove that it is NP-complete, a quick check is to count the number of strings of length $n$ in the language: if the set is sparse it is unlikely to be NPC, otherwise P=NP by <a href="http://en.wikipedia.org/wiki/Sparse_language">Mahaney's theorem</a> ... so it's better to direct efforts towards proving that it is in P :-) :-)</p>

<p>An example is the <a href="http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html">problem of partitioning numbers into k-boxes</a> (from Fortnow &amp; Gasarch's blog, original source: <em>Doctor Ecco's Cyberpuzzles</em>):<br></p>

<p>$\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$</p>

CC BY-SA 3.0
2014-02-06T07:54:04.003Z
2014-02-06T08:03:57.460Z
2014-02-06T08:03:57.460Z
Marzio De Biasi
<p>Here are three additions to Scott's list:</p>

<ul>
<li>Show your problem is in fewP. This means that the number of solutions is bounded by some polynomial. (Example: Turnpike problem). No NP-complete problem is known to be in fewP. (impossible unless fewP=NP).

<li>Show your problem is in $LOGNP$ or in $NP[log^2n]$ (Can be solved using limited number of nondeterministic bits, Example Dominating set problem in tournaments)

<li>Show that your problem has sub-exponential density (H. Buhrman and J. M. Hitchcock proved density lower bound ($2^{n^{\epsilon}}$), unless the polynomial hierarchy collapses. Therefore, any $NP$-complete set must have some $\epsilon \gt 0$ such that for infinitely-many integers $n\ge 0$, the set contains at least $2^{n^{\epsilon}}$ strings of length $n$. ). This is a much stronger than proving just sparsity (as stated in Marzio's answer).
</ul>

<p>H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless $coNP ⊆ NP/poly$, In IEEE Conference on Computational Complexity, pages 1–7, 2008</p>

CC BY-SA 3.0
2014-02-07T00:29:38.920Z
Or even in UP (not just FewP)!
Joshua Grochow
CC BY-SA 3.0
2014-02-06T08:04:10.477Z
2014-02-06T08:29:26.513Z
2014-02-06T08:29:26.513Z
Mohammad Al-Turkistany
<p>Show your problem is in <span class="math-container">$RP$</span> ( hence unlikely to be <span class="math-container">$NP$</span>-hard)</p>
<p>Example:</p>
<p>Exact Perfect Matching problem</p>
<p>Input: A graph G, with each edge colored red or blue, and integer k.</p>
<p>Problem: Decide whether there exists a perfect matching M in G with exactly k red edges</p>

CC BY-SA 4.0
2022-08-18T18:04:06.173Z
This is subsumed by “show that your problem is in BQP” in the top answer.
Emil Jeřábek
CC BY-SA 4.0
2022-08-18T18:08:35.107Z
@EmilJeřábek $RP$ is a subset of $NP$. $BQP$ is not known to be in $NP$. The post about $NP$ problems
Mohammad Al-Turkistany
CC BY-SA 4.0
2022-08-18T17:56:19.373Z
2022-08-18T17:56:19.373Z
Mohammad Al-Turkistany
<p>Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this is difficult:</p>

<ol>
<li>Show that the problem is GI-complete (GI = Graph Isomorphism)</li>
<li>Show that the problem is in $\mathsf{co-AM}$. By known results, such a result implies that if the problem is NP-complete, then PH collapses to the second level. For example, the famous protocol for Graph Nonisomorphism does exactly this.</li>
</ol>

<p>Are there any other methods (maybe with different "strengths of belief") that have been used ? For any answer, an example of where it has actually been used is required: obviously there are many ways one might try to show this, but examples make the argument more convincing. </p>

CC BY-SA 3.0
2014-02-05T22:17:15.273Z
If a problem seems hard enough, but you are not able to prove that it is NPC, a quick check is to count the number of strings of length n in the language: if the set is sparse it is unlikely to be NPC (otherwise P=NP by Mahaney's theorem) ... so it's better to direct efforts towards proving that it is in P :-) :-) An example from [Fortnow & Gasarch's blog](http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html): { (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=z }
Marzio De Biasi
CC BY-SA 3.0
2014-02-06T00:04:36.043Z
@MarzioDeBiasi sounds like an answer to me.
Sasho Nikolov
CC BY-SA 3.0
2014-02-06T10:08:22.430Z
+1 for Ricky Demer; we might want to have a list of methods for the first part.
Pteromys
CC BY-SA 3.0
2014-02-10T09:30:03.030Z
For problems in FNP without obvious decision versions in NP, PPAD is a useful (and growing) class to consider.  PPAD-complete problems include many problems about finding fixed points, for instance Nash equilibria.  Shiva's list is useful: http://www.cs.princeton.edu/~kintali/ppad.html
András Salamon
CC BY-SA 3.0
2014-02-10T18:54:34.400Z
@AndrásSalamon that could be an answer.
Suresh Venkat
CC BY-SA 3.0
2014-02-10T21:32:56.983Z
@SureshVenkat: it seemed tangential, given your clear statement that we are in NP?
András Salamon
CC BY-SA 3.0
2014-02-10T23:25:04.310Z
true. but it's something that comes up as well :)
Suresh Venkat
<cc.complexity-theory><np-hardness><graph-isomorphism><np-intermediate>
Techniques for showing that problem is in hardness "limbo"
Suresh Venkat
# Techniques for showing that problem is in hardness "limbo"

(Asked by: username_0 on 2014-02-05)

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this is difficult:

1. Show that the problem is GI-complete (GI = Graph Isomorphism)
2. Show that the problem is in $\mathsf{co-AM}$. By known results, such a result implies that if the problem is NP-complete, then PH collapses to the second level. For example, the famous protocol for Graph Nonisomorphism does exactly this.

Are there any other methods (maybe with different "strengths of belief") that have been used ? For any answer, an example of where it has actually been used is required: obviously there are many ways one might try to show this, but examples make the argument more convincing.

**Tags:** cc.complexity-theory, np-hardness, graph-isomorphism, np-intermediate
> **Comments:**
> **username_1**: If a problem seems hard enough, but you are not able to prove that it is NPC, a quick check is to count the number of strings of length n in the language: if the set is sparse it is unlikely to be NPC (otherwise P=NP by Mahaney's theorem) ... so it's better to direct efforts towards proving that it is in P :-) :-) An example from [Fortnow & Gasarch's blog](http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html): { (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=z }  
> **username_2**: @MarzioDeBiasi sounds like an answer to me.  
> **username_3**: +1 for Ricky Demer; we might want to have a list of methods for the first part.  
> **username_4**: For problems in FNP without obvious decision versions in NP, PPAD is a useful (and growing) class to consider.  PPAD-complete problems include many problems about finding fixed points, for instance Nash equilibria.  Shiva's list is useful: http://www.cs.princeton.edu/~kintali/ppad.html  
> **username_0**: @AndrásSalamon that could be an answer.  
> **username_4**: @SureshVenkat: it seemed tangential, given your clear statement that we are in NP?  
> **username_0**: true. but it's something that comes up as well :)  

---

## 4 answers

### Answer by username_5 on 2014-02-05. Score: 51

Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo." But besides that, there are several others:

* Show that your problem is in NP ∩ coNP. (Example: Factoring.)* Show that your problem is solvable in quasipolynomial time. (Examples: VC dimension, approximating free games.)* Show that your problem is no harder than inverting one-way functions or solving NP on average. (Examples: Lots of problems in cryptography.)* Show that your problem reduces to (e.g.) Unique Games or Small-Set Expansion.* Show that your problem is in BQP. (Example: Factoring, though of course that's also in NP ∩ coNP.)* Rule out large classes of NP-completeness reductions. (Example: The Circuit Minimization Problem, studied by Kabanets and Cai.)

I'm sure there are others that I'm forgetting.

> **Comments:**
> **username_0**: That's an excellent list, Scott !  
> **username_5**: Philip: You're right, they don't.  For adducing evidence that a particular NP problem is not in P, it all boils down to (1) trying to put it in P and failing, and/or (2) reducing other problems that people failed to put in P to that problem.  

---

### Answer by username_1 on 2014-02-06. Score: 28

From the comment above: if a problem seems hard enough, but you are not able to prove that it is NP-complete, a quick check is to count the number of strings of length $n$ in the language: if the set is sparse it is unlikely to be NPC, otherwise P=NP by [Mahaney's theorem](http://en.wikipedia.org/wiki/Sparse_language) ... so it's better to direct efforts towards proving that it is in P :-) :-)

An example is the [problem of partitioning numbers into k-boxes](http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html) (from Fortnow & Gasarch's blog, original source: *Doctor Ecco's Cyberpuzzles*):

$\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$


---

### Answer by username_6 on 2014-02-06. Score: 24

Here are three additions to Scott's list:

* Show your problem is in fewP. This means that the number of solutions is bounded by some polynomial. (Example: Turnpike problem). No NP-complete problem is known to be in fewP. (impossible unless fewP=NP).* Show your problem is in $LOGNP$ or in $NP[log^2n]$ (Can be solved using limited number of nondeterministic bits, Example Dominating set problem in tournaments)* Show that your problem has sub-exponential density (H. Buhrman and J. M. Hitchcock proved density lower bound ($2^{n^{\epsilon}}$), unless the polynomial hierarchy collapses. Therefore, any $NP$-complete set must have some $\epsilon \gt 0$ such that for infinitely-many integers $n\ge 0$, the set contains at least $2^{n^{\epsilon}}$ strings of length $n$. ). This is a much stronger than proving just sparsity (as stated in Marzio's answer).

H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless $coNP ⊆ NP/poly$, In IEEE Conference on Computational Complexity, pages 1–7, 2008

> **Comments:**
> **username_7**: Or even in UP (not just FewP)!  

---

### Answer by username_6 on 2022-08-18. Score: 0

Show your problem is in $RP$ ( hence unlikely to be $NP$-hard)

Example:

Exact Perfect Matching problem

Input: A graph G, with each edge colored red or blue, and integer k.

Problem: Decide whether there exists a perfect matching M in G with exactly k red edges

> **Comments:**
> **username_8**: This is subsumed by “show that your problem is in BQP” in the top answer.  
> **username_6**: @EmilJeřábek $RP$ is a subset of $NP$. $BQP$ is not known to be in $NP$. The post about $NP$ problems  

---

