<p>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.</p>

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

<p>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?</p>

CC BY-SA 3.0
2015-04-11T02:03:39.380Z
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....
D.W.
CC BY-SA 3.0
2015-04-13T13:06:00.793Z
@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.
Vanessa
CC BY-SA 3.0
2015-04-13T13:09:46.883Z
@PhilipWhite Normally padding arguments go the other way, e.g. $EXP \ne NEXP$ implies $P \ne NP$ but not the other way around.
Vanessa
<cc.complexity-theory><exp-time-algorithms><average-case-complexity><nexp>
What is the evidence for average case separation between EXP and NEXP?
Vanessa
# What is the evidence for average case separation between EXP and NEXP?

(Asked by: username_0 on 2015-04-10)

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?

**Tags:** cc.complexity-theory, exp-time-algorithms, average-case-complexity, nexp
> **Comments:**
> **username_1**: 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....  
> **username_0**: @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.  
> **username_0**: @PhilipWhite Normally padding arguments go the other way, e.g. $EXP \ne NEXP$ implies $P \ne NP$ but not the other way around.  

---

## 0 answers

