2026-07-22T10:51:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15641 2024-03-06T10:55:50Z ddc:004 open_access

Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions Chen, Lijie Hirahara, Shuichi Vafa, Neekon Average-case complexity worst-case to average-case reduction 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: - NTIME[n] cannot be solved in quasi-linear time on average if UP ̸ ⊆ DTIME[2^{Õ(√n)}]. - Σ₂TIME[n] cannot be solved in quasi-linear time on average if Σ_kSAT cannot be solved in time 2^{Õ(√n)} for some constant k. Previously, it was not known if even average-case hardness of Σ₃SAT implies the average-case hardness of Σ₂TIME[n]. - Under the Exponential-Time Hypothesis (ETH), there is no average-case n^{1+ε}-time algorithm for NTIME[n] whose running time can be estimated in time n^{1+ε} for some constant ε > 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lijie Chen and Shuichi Hirahara and Neekon Vafa 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.45 urn:nbn:de:0030-drops-156411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.45 eng https://creativecommons.org/licenses/by/4.0/legalcode