<p>1) Depending on exactly what was meant, the conclusion in Kaveh's observation can be strengthened from $\mathsf{NP} \subseteq \mathsf{P/poly}$ to $\mathsf{P} = \mathsf{NP}$, essentially using Mahaney's Theorem. That is, if there is an algorithm which solves SAT and runs in time $\leq p(n)$ on all instances of length $n$ except for possibly $q(n)$ such instances, where $p$ and $q$ are both polynomials, then in fact $\mathsf{P} = \mathsf{NP}$. See, e.g. <a href="http://www.dcs.warwick.ac.uk/~msp/papers/MIT-LCS-TM-126.pdf">Meyer and Paterson</a> and references therein, or <a href="http://www.ams.org/mathscinet-getitem?mr=827009">Schoning's monograph "Complexity and Structure"</a>. So if this captures your notion of "hard instances" then there must be more than $poly(n)$ many hard instances for each $n$, assuming $\mathsf{P} \neq \mathsf{NP}$. </p>

<p>FYI, such algorithms are sometimes referred to as "apt" or "APT" algorithms, for "almost polynomial time" (not to be confused with the more modern complexity class $\mathsf{almostP}$, which happens to equal $\mathsf{BPP}$). </p>

<p>2) The above can be strengthened even further, as follows. Assume $\mathsf{P} \neq \mathsf{NP}$. Then the above says that for any algorithm solving SAT and any polynomial $p$, there is a set of instances of super-polynomial size on which the algorithm takes more than $p(n)$ time. But the set can depend on the algorithm.</p>

<p>The stronger result switches the quantifiers, and concludes: there is a super-polynomial size set H (for "hard") such that for any algorithm A solving SAT and any polynomial p, A takes more than $p(n)$ time on all but finitely many elements of H. Such an H is called a <strong>complexity core</strong> (the size assumption is not part of the definition of complexity core). The definition and existence of complexity cores was given by <a href="http://dx.doi.org/10.1145/321892.321895">Lynch</a>. The result I just quoted is proved by <a href="http://dx.doi.org/10.1016/S0019-9958(86)80024-9">Orponen and Schoning</a>.</p>

CC BY-SA 3.0
2013-05-21T05:53:12.063Z
2013-05-21T05:53:12.063Z
Joshua Grochow
<p>Nobody has mentioned Impagliazzo's famous "Five worlds" paper.</p>

<p><a href="http://www.cs.ucsd.edu/users/russell/average.ps" rel="nofollow">http://www.cs.ucsd.edu/users/russell/average.ps</a></p>

CC BY-SA 3.0
2013-06-08T07:32:03.503Z
This was referenced by the very first comment?
András Salamon
CC BY-SA 3.0
2013-06-08T01:45:54.100Z
2013-06-08T01:45:54.100Z
none
<p>another angle on this question (outside of the ref to Mahaney's theorem). the "transition point" in SAT is a study of this phenomena of easy vs hard instance distribution esp around a "critical point" where probability of hard instances is maximized. the literature on the subject is long and complex. it has both empirical and analytical approaches. it has deep ties to physics/thermodynamics.[3] unfortunately there is currently no Wikipedia entry on this very significant and fundamental complexity theory topic. also, there do not seem to be many overall or "standard" surveys on the subject. here is one recent ref to start on SAT[1] and TCS phase transitions in general.[4] your question also falls into a category of "a really good answer would basically be nearly a P$\stackrel{?}{=}$NP proof."</p>

<blockquote>
  <p>Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?</p>
</blockquote>

<p>again Mahaney's theorem (phrased in a slightly different way) answers this directly. another way of looking at this is that attempts to narrow the distribution of instances in some key/characteristic way leads to NP-complete functions. an example of this from monotone circuit complexity is "slice functions".[2]</p>

<p>[1] <a href="http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf" rel="nofollow">Predicting Satisfiability at the Phase Transition</a> Lin Xu, Holger H. Hoos, Kevin Leyton-Brown</p>

<p>[2] Paul E. S. Dunne: The Complexity of Central Slice Functions. Theor. Comput. Sci. 44: 247-257 (1986)</p>

<p>[3] <a href="http://dynamics.org/~altenber/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf" rel="nofollow">Analytic and Algorithmic
Solution of Random
Satisfiability Problems</a>
M. Mezard,
G. Parisi,
R. Zecchina</p>

<p>[4] <a href="http://www.math.ucla.edu/~roch/ams2010_files/moore.pdf" rel="nofollow">Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science</a> by Moore</p>

CC BY-SA 3.0
2013-05-22T17:34:13.387Z
2013-05-22T17:34:13.387Z
vzn
<p>Suppose P != NP.</p>

<p>We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?</p>

<p>For any hard 3-SAT instance, we would have to add the set of all 3-SAT instances it reduces to via looping through the NP-Completeness reduction cycle, but I don't foresee this adding to the number of hard instances very much.</p>

<p>In this world, we could construct an algorithm that polynomially solves all NP complete problems, except an exceptional few.</p>

<p>Edit:
A softer variant of the question: even if we showed P!=NP, how could we know whether a given method to generate size n 3-SAT problems actually generated hard one with some requisite probability?  If there's no way to know from P!=NP alone, what is required to show that we can generate a hard NP-complete problem?</p>

CC BY-SA 3.0
2013-05-18T10:23:42.963Z
Yes. NP-complete problems are hard in the worst-case. It is possible that the majority of instances of an NP-complete problem are efficiently solvable. However, Russell Impagliazzo proposed a world (Pessiland) where average-case NP-complete problems exist but one-way functions do not exist. In this world, we can not generate hard instances of NP-complete problem with known solution.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-18T10:40:35.773Z
So what I'm really asking about is the one-way function problem? How large is the evidence for one-way functions?
Elliot JJ
CC BY-SA 3.0
2013-05-18T10:42:35.280Z
Short answer, $P \ne NP$ assumption alone is not helpful. We need at least the existence of one-way functions.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-18T10:52:12.670Z
As for the evidence for one-way functions, see this post: http://cstheory.stackexchange.com/questions/8829/arguments-for-existence-of-one-way-functions
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-18T10:56:59.023Z
If the set of hard instances of each length is polynomially small then NP is contained in P/poly. There are also other ways of looking at this, search for HeurP.
Kaveh
CC BY-SA 3.0
2013-05-18T12:35:56.033Z
[This question](http://cstheory.stackexchange.com/questions/17456/the-examiners-problem-uniform-generation-of-sat-decision-instances-answers) seems to address your edit -- we can (determinstically) generate hard instances of SAT if and only if unary $\mathsf{NP} \neq$ unary $\mathsf{P}$.
usul
CC BY-SA 3.0
2013-05-19T04:00:47.850Z
I think it is possible that all NP problems are in non-uniform P, while uniform NP is not equal to uniform P. Non-uniform means that we parametrize the algorithm by the input size, and allow them to change with the input size. This makes things much more difficult - people looked at this in the context of circuits.
Sariel Har-Peled
CC BY-SA 3.0
2013-05-19T05:23:44.993Z
@SarielHar-Peled In particular, NP $\subseteq$ P/poly collapses PH to the second level, which is consistent with P != NP.
Suresh Venkat
CC BY-SA 3.0
2013-05-19T14:43:34.790Z
There is no known way to connect worst-case and average-case hardness of NP.  However there are ways to connect "mild" average-case hardness to "strong" average-case hardness.  My thesis is a starting point for both.  http://www.ccs.neu.edu/home/viola/papers/thesis.pdf
Manu
CC BY-SA 3.0
2013-05-21T15:13:59.997Z
seems to me the big part of this question is around technically defining "large hidden subset". and its possibly more talking about the _density_ of easy vs hard instances. also feel this question is largely answered by research on the SAT transition point.
vzn
<np-hardness><p-vs-np>
Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?
Elliot JJ
# Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

(Asked by: username_0 on 2013-05-18)

Suppose P != NP.

We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?

For any hard 3-SAT instance, we would have to add the set of all 3-SAT instances it reduces to via looping through the NP-Completeness reduction cycle, but I don't foresee this adding to the number of hard instances very much.

In this world, we could construct an algorithm that polynomially solves all NP complete problems, except an exceptional few.

Edit:
A softer variant of the question: even if we showed P!=NP, how could we know whether a given method to generate size n 3-SAT problems actually generated hard one with some requisite probability? If there's no way to know from P!=NP alone, what is required to show that we can generate a hard NP-complete problem?

**Tags:** np-hardness, p-vs-np

> **Comments:**
> **username_1**: Yes. NP-complete problems are hard in the worst-case. It is possible that the majority of instances of an NP-complete problem are efficiently solvable. However, Russell Impagliazzo proposed a world (Pessiland) where average-case NP-complete problems exist but one-way functions do not exist. In this world, we can not generate hard instances of NP-complete problem with known solution.  
> **username_0**: So what I'm really asking about is the one-way function problem? How large is the evidence for one-way functions?  
> **username_1**: Short answer, $P \ne NP$ assumption alone is not helpful. We need at least the existence of one-way functions.  
> **username_1**: As for the evidence for one-way functions, see this post: http://cstheory.stackexchange.com/questions/8829/arguments-for-existence-of-one-way-functions  
> **username_2**: If the set of hard instances of each length is polynomially small then NP is contained in P/poly. There are also other ways of looking at this, search for HeurP.  
> **username_3**: [This question](http://cstheory.stackexchange.com/questions/17456/the-examiners-problem-uniform-generation-of-sat-decision-instances-answers) seems to address your edit -- we can (determinstically) generate hard instances of SAT if and only if unary $\mathsf{NP} \neq$ unary $\mathsf{P}$.  
> **username_4**: I think it is possible that all NP problems are in non-uniform P, while uniform NP is not equal to uniform P. Non-uniform means that we parametrize the algorithm by the input size, and allow them to change with the input size. This makes things much more difficult - people looked at this in the context of circuits.  
> **username_5**: @SarielHar-Peled In particular, NP $\subseteq$ P/poly collapses PH to the second level, which is consistent with P != NP.  
> **username_6**: There is no known way to connect worst-case and average-case hardness of NP.  However there are ways to connect "mild" average-case hardness to "strong" average-case hardness.  My thesis is a starting point for both.  http://www.ccs.neu.edu/home/viola/papers/thesis.pdf  
> **username_7**: seems to me the big part of this question is around technically defining "large hidden subset". and its possibly more talking about the _density_ of easy vs hard instances. also feel this question is largely answered by research on the SAT transition point.  

---

## 3 answers

### Answer by username_8 on 2013-05-21. Score: 12

1) Depending on exactly what was meant, the conclusion in username_2's observation can be strengthened from $\mathsf{NP} \subseteq \mathsf{P/poly}$ to $\mathsf{P} = \mathsf{NP}$, essentially using Mahaney's Theorem. That is, if there is an algorithm which solves SAT and runs in time $\leq p(n)$ on all instances of length $n$ except for possibly $q(n)$ such instances, where $p$ and $q$ are both polynomials, then in fact $\mathsf{P} = \mathsf{NP}$. See, e.g. [Meyer and Paterson](http://www.dcs.warwick.ac.uk/~msp/papers/MIT-LCS-TM-126.pdf) and references therein, or [Schoning's monograph "Complexity and Structure"](http://www.ams.org/mathscinet-getitem?mr=827009). So if this captures your notion of "hard instances" then there must be more than $poly(n)$ many hard instances for each $n$, assuming $\mathsf{P} \neq \mathsf{NP}$.

FYI, such algorithms are sometimes referred to as "apt" or "APT" algorithms, for "almost polynomial time" (not to be confused with the more modern complexity class $\mathsf{almostP}$, which happens to equal $\mathsf{BPP}$).

2) The above can be strengthened even further, as follows. Assume $\mathsf{P} \neq \mathsf{NP}$. Then the above says that for any algorithm solving SAT and any polynomial $p$, there is a set of instances of super-polynomial size on which the algorithm takes more than $p(n)$ time. But the set can depend on the algorithm.

The stronger result switches the quantifiers, and concludes: there is a super-polynomial size set H (for "hard") such that for any algorithm A solving SAT and any polynomial p, A takes more than $p(n)$ time on all but finitely many elements of H. Such an H is called a **complexity core** (the size assumption is not part of the definition of complexity core). The definition and existence of complexity cores was given by [Lynch](http://dx.doi.org/10.1145/321892.321895). The result I just quoted is proved by [Orponen and Schoning](http://dx.doi.org/10.1016/S0019-9958(86)80024-9).


---

### Answer by username_9 on 2013-06-08. Score: 0

Nobody has mentioned Impagliazzo's famous "Five worlds" paper.

<http://www.cs.ucsd.edu/users/russell/average.ps>

> **Comments:**
> **username_10**: This was referenced by the very first comment?  

---

### Answer by username_7 on 2013-05-22. Score: -3

another angle on this question (outside of the ref to Mahaney's theorem). the "transition point" in SAT is a study of this phenomena of easy vs hard instance distribution esp around a "critical point" where probability of hard instances is maximized. the literature on the subject is long and complex. it has both empirical and analytical approaches. it has deep ties to physics/thermodynamics.[3] unfortunately there is currently no Wikipedia entry on this very significant and fundamental complexity theory topic. also, there do not seem to be many overall or "standard" surveys on the subject. here is one recent ref to start on SAT[1] and TCS phase transitions in general.[4] your question also falls into a category of "a really good answer would basically be nearly a P$\stackrel{?}{=}$NP proof."

> Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?

again Mahaney's theorem (phrased in a slightly different way) answers this directly. another way of looking at this is that attempts to narrow the distribution of instances in some key/characteristic way leads to NP-complete functions. an example of this from monotone circuit complexity is "slice functions".[2]

[1] [Predicting Satisfiability at the Phase Transition](http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf) Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

[2] Paul E. S. Dunne: The Complexity of Central Slice Functions. Theor. Comput. Sci. 44: 247-257 (1986)

[3] [Analytic and Algorithmic
Solution of Random
Satisfiability Problems](http://dynamics.org/~altenber/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf)
M. Mezard,
G. Parisi,
R. Zecchina

[4] [Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science](http://www.math.ucla.edu/~roch/ams2010_files/moore.pdf) by Moore


---

