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$)
$\begingroup$
$\endgroup$
1
-
$\begingroup$ See this surprising conjecture, which is significantly more plausible than its statement sounds, for reasons explained by the article. $\endgroup$– user6973Oct 26, 2016 at 8:03
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. 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.
answered Oct 25, 2016 at 21:43
-
$\begingroup$ That's really cool, thanks :). For completeness, those assumptions are: pseudorandom generators exist and secure one-way permutations exist $\endgroup$ Oct 26, 2016 at 4:51
-
$\begingroup$ @Phylliida : Note that those are using some complexity-theoretic definition for "pseudorandom generator", rather than a usual cryptographic definition. $\endgroup$– user6973Oct 26, 2016 at 5:07
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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 $\endgroup$ Oct 25, 2016 at 21:46