ECCC-Report TR21-166https://eccc.weizmann.ac.il/report/2021/166Comments and Revisions published for TR21-166en-usSun, 21 Nov 2021 03:35:02 +0200
Paper TR21-166
| Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions |
Lijie Chen,
Shuichi Hirahara,
Neekon Vafa
https://eccc.weizmann.ac.il/report/2021/166 What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness of NP or PH:
1. NTIME[$n$] cannot be solved in quasi-linear time on average if UP is not in DTIME[$2^{\widetilde{O}\left(\sqrt{n}\right)}$].
2. $\Sigma_2$TIME[$n$] cannot be solved in quasi-linear time on average if $\Sigma_k$SAT cannot be solved in time $2^{\widetilde{O}\left(\sqrt{n}\right)}$ for some constant $k$. Previously, it was not known if even average-case hardness of $\Sigma_3$SAT implies the average-case hardness of $\Sigma_2$TIME[$n$].
3. Under the Exponential-Time Hypothesis (ETH), there is no average-case $n^{1+\varepsilon}$-time algorithm for NTIME[$n$] whose running time can be estimated in time $n^{1+\varepsilon}$ for some constant $\varepsilon > 0$.
Our results are given by generalizing the non-black-box worst-case-to-average-case connections presented by Hirahara (STOC 2021) to the settings of fine-grained complexity. To do so, we construct quite efficient complexity-theoretic pseudorandom generators under the assumption that the nondeterministic linear time is easy on average, which may be of independent interest. Sun, 21 Nov 2021 03:35:02 +0200https://eccc.weizmann.ac.il/report/2021/166