<p>A first observation is that having exactly what you ask would be a proof that $P \neq NP$ as it would imply that the set of all instances can not be solved in polynomial time.</p>

<p>However, and I think that is what you meant, we can play a bit with what we mean by "solved in polynomial time". If we mean by it all infinite subsets $\phi$ of instances whose membership is in $P$ are $NP$-complete, then the answer is no by Mahaney's Theorem (<a href="http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute-to-mahaney.html" rel="nofollow">http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute-to-mahaney.html</a>). This theorem states that no NP-complete problem can be sparse unless $P = NP$. Now, taking the subset of instances $\{0^i \mid i \in \mathbb{N}\}$, we have an infinite sparse subset of instances for which testing membership is in $P$ that cannot be $NP$-complete unless $P = NP$ by Mahaney's Theorem.</p>

CC BY-SA 3.0
2016-10-25T21:46:02.533Z
Ah sorry, what I meant is that they can't be solved in polynomial time assuming $P \neq NP$, you're right that that is very important
Phylliida
CC BY-SA 3.0
2016-10-25T21:42:54.427Z
2016-10-25T21:42:54.427Z
holf
<p>See Josh Grochow's answer to <a href="https://cstheory.stackexchange.com/questions/33312/poly-time-superset-of-np-complete-language-with-infinitely-many-strings-excluded/33316#33316">Poly time superset of NP complete language with infinitely many strings excluded from it</a>. According to that answer, under some natural cryptographic assumptions, for every co-NP-complete problem there is an infinite subset $\Phi$ of instances such that membership in $\Phi$ is polynomial time, and the decision problem restricted to $\Phi$ is trivial (answer always no).</p>

<p>This can be formalized by stating that no co-NP-complete set is P-immune. It is also known (again under cryptographic assumptions) that no NP-complete set is P-immune. So there is another infinite subset $\Phi'$ such that membership in $\Phi'$ is polynomial-time testable and the decision problem restricted to $\Phi'$ always has answer yes. See e.g. Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, <a href="http://doi.org/10.1137/S009753970444421X" rel="nofollow noreferrer">doi:10.1137/S009753970444421X</a>.</p>

CC BY-SA 3.0
2016-10-26T04:51:36.820Z
That's really cool, thanks :). For completeness, those assumptions are: pseudorandom generators exist and secure one-way permutations exist
Phylliida
CC BY-SA 3.0
2016-10-25T21:43:28.917Z
2016-10-25T21:43:28.917Z
2017-04-13T12:32:28.117Z
David Eppstein
<p>Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in polynomial time? (Assuming $P \neq NP$)</p>

<cc.complexity-theory><np-complete><heuristics>
Are there any heuristic-free NP complete problems?
Phylliida
# Are there any heuristic-free NP complete problems?

(Asked by: username_0 on 2016-10-25)

Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in polynomial time? (Assuming $P \neq NP$)

**Tags:** cc.complexity-theory, np-complete, heuristics

---

## 2 answers

### Answer by username_2 on 2016-10-25. Score: 16 | Accepted answer

See Josh Grochow's answer to [Poly time superset of NP complete language with infinitely many strings excluded from it](https://cstheory.stackexchange.com/questions/33312/poly-time-superset-of-np-complete-language-with-infinitely-many-strings-excluded/33316#33316). According to that answer, under some natural cryptographic assumptions, for every co-NP-complete problem there is an infinite subset $\Phi$ of instances such that membership in $\Phi$ is polynomial time, and the decision problem restricted to $\Phi$ is trivial (answer always no).

This can be formalized by stating that no co-NP-complete set is P-immune. It is also known (again under cryptographic assumptions) that no NP-complete set is P-immune. So there is another infinite subset $\Phi'$ such that membership in $\Phi'$ is polynomial-time testable and the decision problem restricted to $\Phi'$ always has answer yes. See e.g. Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, [doi:10.1137/S009753970444421X](http://doi.org/10.1137/S009753970444421X).

> **Comments:**
> **username_0**: That's really cool, thanks :). For completeness, those assumptions are: pseudorandom generators exist and secure one-way permutations exist  

---

### Answer by username_1 on 2016-10-25. Score: 0

A first observation is that having exactly what you ask would be a proof that $P \neq NP$ as it would imply that the set of all instances can not be solved in polynomial time.

However, and I think that is what you meant, we can play a bit with what we mean by "solved in polynomial time". If we mean by it all infinite subsets $\phi$ of instances whose membership is in $P$ are $NP$-complete, then the answer is no by Mahaney's Theorem (<http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute-to-mahaney.html>). This theorem states that no NP-complete problem can be sparse unless $P = NP$. Now, taking the subset of instances $\{0^i \mid i \in \mathbb{N}\}$, we have an infinite sparse subset of instances for which testing membership is in $P$ that cannot be $NP$-complete unless $P = NP$ by Mahaney's Theorem.

> **Comments:**
> **username_0**: Ah sorry, what I meant is that they can't be solved in polynomial time assuming $P \neq NP$, you're right that that is very important  

---

