<p>This is a slightly improved version of my two comments on the question combined.</p>

<p>Let’s restrict our attention to distributional problems in <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aD#distnp">DistNP</a> (aka (NP, P-computable)) for simplicity.  Then you are looking for a problem in DistNP ∖ Average-P/poly.  Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly.  And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under average-case reductions.</p>

<p>(Considering a larger class SampNP (aka <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aN#nppsamp">(NP, P-samplable)</a>) instead of DistNP does not change the situation much because DistNP ⊆ Average-P/poly if and only if SampNP ⊆ Average-P/poly.  This equivalence is a direct corollary of the result by Impagliazzo and Levin [IL90] that every distributional problem in SampNP is average-case reducible to some distributional problem in DistNP.)</p>

<p>I do not know which natural assumption implies DistNP ⊈ Average-P/poly.  The assumption that the polynomial hierarchy does not collapse is not known to imply even a weaker consequence that DistNP ⊈ Average-P, according to Section 18.4 of Arora and Barak [AB09]: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”</p>

<h3>References</h3>

<p>[AB09] Sanjeev Arora and Boaz Barak.  <em>Computational Complexity: A Modern Approach</em>, Cambridge University Press, 2009.</p>

<p>[IL90] Russell Impagliazzo and Leonid A. Levin.  No better ways to generate hard NP instances than picking uniformly at random.  In <em>the 31st Annual Symposium on Foundations of Computer Science</em>, 812–821, Oct. 1990.  <a href="http://dx.doi.org/10.1109/FSCS.1990.89604">http://dx.doi.org/10.1109/FSCS.1990.89604</a></p>

CC BY-SA 2.5
2011-02-25T13:06:37.867Z
2011-02-25T13:06:37.867Z
Tsuyoshi Ito
<p>The <a href="http://en.wikipedia.org/wiki/Karp-Lipton_theorem" rel="noreferrer">Karp–Lipton Theoem</a> states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\mathsf{\Sigma^P_3}$, no $\mathsf{NP}$-complete problem will belong to $\mathsf{P/poly}$.</p>

<p>I'm interested in the following question:</p>

<blockquote>
  <p>Assuming that $\mathsf{PH}$ does not collapse, or assuming any other reasonable assumption in structural complexity, what <strong>hard-on-average</strong> $\mathsf{NP}$ problems are <em>proven</em> not to lie in $\mathsf{Average\mbox{-}P/poly}$ (if any)?</p>
</blockquote>

<p>A definition of $\mathsf{Average\mbox{-}P/poly}$ can be found in <a href="http://www.cse.unl.edu/~vinod/papers/fct05.ps" rel="noreferrer">Relations between Average-case and Worst-case Complexity</a>. Thanks to Tsuyoshi for pointing out that I actually need to use $\mathsf{Average\mbox{-}P/poly}$ instead of $\mathsf{P/poly}$.</p>

<p>I <em>think</em> there are problems such as (the decision versions of) <a href="http://en.wikipedia.org/wiki/Integer_factorization" rel="noreferrer">FACTORING</a> or <a href="http://en.wikipedia.org/wiki/Discrete_logarithm" rel="noreferrer">DLOG</a> which are conjectured to lie in $\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$, but the conjecture is not proven based on separations between complexity classes. (Please correct me if I'm wrong.)</p>

CC BY-SA 2.5
2011-02-23T23:34:51.107Z
(1) I do not think that the assumption that the polynomial hierarchy does not collapse is known to imply that there is a hard-on-average problem in NP.  Section 18.4 of Arora and Barak states: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-23T23:35:38.050Z
(2) Is P/poly in the question the usual one with worst-case complexity, or are you considering an average-case analogue of it?  If it is the worst-case one, then you need both DistP≠DistNP and NP⊈P/poly to have such a problem, and if these hold, then every DistNP-complete problem satisfies the requirement because a DistNP-complete problem is necessarily NP-complete if we throw away the input distribution.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-24T04:18:55.260Z
@Tsuyoshi: Thanks a lot. You do have a point about the worst-case vs. average-case P/poly. On a second thought (about the original problem), I think I have to interpret P/poly as an **average-case** class.
Sadeq Dousti
CC BY-SA 2.5
2011-02-24T14:17:14.370Z
I read the revision 3.  Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly.  And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under reductions (between distributional problems).  But maybe you are asking for a more natural problem under a stronger assumption.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-24T17:31:07.153Z
@Tsuyoshi: Thank you. Could you make the comments into an answer so that I can accept it?
Sadeq Dousti
CC BY-SA 2.5
2011-02-25T13:06:55.433Z
@Sadeq: Done. -
Tsuyoshi Ito
<cc.complexity-theory><np><conditional-results><advice-and-nonuniformity><average-case-complexity>
Problems in NP but not in Average-P/poly
Sadeq Dousti
# Problems in NP but not in Average-P/poly

(Asked by: username_0 on 2011-02-23)

The [Karp–Lipton Theoem](http://en.wikipedia.org/wiki/Karp-Lipton_theorem) states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P\_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P\_2}$ and $\mathsf{\Sigma^P\_3}$, no $\mathsf{NP}$-complete problem will belong to $\mathsf{P/poly}$.

I'm interested in the following question:

> Assuming that $\mathsf{PH}$ does not collapse, or assuming any other reasonable assumption in structural complexity, what **hard-on-average** $\mathsf{NP}$ problems are *proven* not to lie in $\mathsf{Average\mbox{-}P/poly}$ (if any)?

A definition of $\mathsf{Average\mbox{-}P/poly}$ can be found in [Relations between Average-case and Worst-case Complexity](http://www.cse.unl.edu/~vinod/papers/fct05.ps). Thanks to Tsuyoshi for pointing out that I actually need to use $\mathsf{Average\mbox{-}P/poly}$ instead of $\mathsf{P/poly}$.

I *think* there are problems such as (the decision versions of) [FACTORING](http://en.wikipedia.org/wiki/Integer_factorization) or [DLOG](http://en.wikipedia.org/wiki/Discrete_logarithm) which are conjectured to lie in $\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$, but the conjecture is not proven based on separations between complexity classes. (Please correct me if I'm wrong.)

**Tags:** cc.complexity-theory, np, conditional-results, advice-and-nonuniformity, average-case-complexity

> **Comments:**
> **username_1**: (1) I do not think that the assumption that the polynomial hierarchy does not collapse is known to imply that there is a hard-on-average problem in NP.  Section 18.4 of Arora and Barak states: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”  
> **username_1**: (2) Is P/poly in the question the usual one with worst-case complexity, or are you considering an average-case analogue of it?  If it is the worst-case one, then you need both DistP≠DistNP and NP⊈P/poly to have such a problem, and if these hold, then every DistNP-complete problem satisfies the requirement because a DistNP-complete problem is necessarily NP-complete if we throw away the input distribution.  
> **username_0**: @Tsuyoshi: Thanks a lot. You do have a point about the worst-case vs. average-case P/poly. On a second thought (about the original problem), I think I have to interpret P/poly as an **average-case** class.  
> **username_1**: I read the revision 3.  Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly.  And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under reductions (between distributional problems).  But maybe you are asking for a more natural problem under a stronger assumption.  
> **username_0**: @Tsuyoshi: Thank you. Could you make the comments into an answer so that I can accept it?  
> **username_1**: @Sadeq: Done. -  

---

## 1 answers

### Answer by username_1 on 2011-02-25. Score: 7 | Accepted answer

This is a slightly improved version of my two comments on the question combined.

Let’s restrict our attention to distributional problems in [DistNP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aD#distnp) (aka (NP, P-computable)) for simplicity. Then you are looking for a problem in DistNP ∖ Average-P/poly. Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly. And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under average-case reductions.

(Considering a larger class SampNP (aka [(NP, P-samplable)](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aN#nppsamp)) instead of DistNP does not change the situation much because DistNP ⊆ Average-P/poly if and only if SampNP ⊆ Average-P/poly. This equivalence is a direct corollary of the result by Impagliazzo and Levin [IL90] that every distributional problem in SampNP is average-case reducible to some distributional problem in DistNP.)

I do not know which natural assumption implies DistNP ⊈ Average-P/poly. The assumption that the polynomial hierarchy does not collapse is not known to imply even a weaker consequence that DistNP ⊈ Average-P, according to Section 18.4 of Arora and Barak [AB09]: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”

### References

[AB09] Sanjeev Arora and Boaz Barak. *Computational Complexity: A Modern Approach*, Cambridge University Press, 2009.

[IL90] Russell Impagliazzo and Leonid A. Levin. No better ways to generate hard NP instances than picking uniformly at random. In *the 31st Annual Symposium on Foundations of Computer Science*, 812–821, Oct. 1990. <http://dx.doi.org/10.1109/FSCS.1990.89604>


---

