There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way functions and candidate pseudorandom generators.

Is there similar evidence for an average case analogue of the separation between EXP and NEXP?

EDIT: I have the outline of the argument implying the above separation but the conclusion seems too strong so I suspect there is an error somewhere. The separation between $EXP$ and $NEXP$ corresponds to the separation between $P$ and $NP \cap TALLY$ via unary encoding. Given a language $L \in TALLY$ we can construct the language $L':=\lbrace x | 1^{|x|} \in L \rbrace$. However, it seems that the existence of a heuristic algorithm for $L'$ wrt the uniform distribution implies that $L \in BPP$. Hence, $BPP \nsupseteq NP \cap SPARSE$ implies $HeurP \nsupseteq DistNP$. However, if such a simple average-case to worst-case reduction existed I would probably have encountered it in the literature by now, so I must have got something wrong. What is going on?

  • 2
    $\begingroup$ Tiny nitpick: Candidate one-way functions and/or pseudorandom generators do yield good candidates for problems that are in NP but not P. Whether those problems are NP-complete is another matter. For instance, one-way functions based upon factorization seem likely to yield problems that are in NP, but not in P and not NP-complete. That said, there might be other candidate one-way functions with no obvious barriers to NP-completeness (say, AES). Anyway, it seems like you don't require NP-completeness, merely being in NP but not P. I realize this doesn't answer your question.... $\endgroup$ – D.W. Apr 11 '15 at 2:03
  • $\begingroup$ Do you think the standard padding argument has any relevance here? $\endgroup$ – Philip White Apr 11 '15 at 3:29
  • $\begingroup$ @D.W. I didn't claim those problems are NP-complete. I meant that the existence of one-way functions implies that $AvgP \nsupseteq DistNP$ which implies that problems complete for $DistNP$ are hard in the average case. $\endgroup$ – Squark Apr 13 '15 at 13:06
  • $\begingroup$ @PhilipWhite Normally padding arguments go the other way, e.g. $EXP \ne NEXP$ implies $P \ne NP$ but not the other way around. $\endgroup$ – Squark Apr 13 '15 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.