20
$\begingroup$

The Karp–Lipton Theoem 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. 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 or DLOG 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.)

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ (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.” $\endgroup$
    – Tsuyoshi Ito
    Feb 23, 2011 at 23:34
  • 3
    $\begingroup$ (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. $\endgroup$
    – Tsuyoshi Ito
    Feb 23, 2011 at 23:35
  • $\begingroup$ @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. $\endgroup$
    – Sadeq Dousti
    Feb 24, 2011 at 4:18
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Feb 24, 2011 at 14:17
  • $\begingroup$ @Tsuyoshi: Thank you. Could you make the comments into an answer so that I can accept it? $\endgroup$
    – Sadeq Dousti
    Feb 24, 2011 at 17:31

1 Answer 1

Reset to default
7
$\begingroup$

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

Let’s restrict our attention to distributional problems in 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)) 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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.