2026-07-23T06:06:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16587 2024-03-06T10:57:52Z ddc:004 open_access

Finding Errorless Pessiland in Error-Prone Heuristica Hirahara, Shuichi Nanashima, Mikito average-case complexity oracle separation relativization barrier meta-complexity learning auxiliary-input cryptography Average-case complexity has two standard formulations, i.e., errorless complexity and error-prone complexity. In average-case complexity, a critical topic of research is to show the equivalence between these formulations, especially on the average-case complexity of NP. In this study, we present a relativization barrier for such an equivalence. Specifically, we construct an oracle relative to which NP is easy on average in the error-prone setting (i.e., DistNP ⊆ HeurP) but hard on average in the errorless setting even by 2^o(n/log n)-size circuits (i.e., DistNP ⊈ AvgSIZE[2^o(n/log n)]), which provides an answer to the open question posed by Impagliazzo (CCC 2011). Additionally, we show the following in the same relativized world: - Lower bound of meta-complexity: GapMINKT^𝒪 ∉ prSIZE^𝒪[2^o(n/log n)] and GapMCSP^𝒪 ∉ prSIZE^𝒪[2^(n^ε)] for some ε > 0. - Worst-case hardness of learning on uniform distributions: P/poly is not weakly PAC learnable with membership queries on the uniform distribution by nonuniform 2ⁿ/n^ω(1)-time algorithms. - Average-case hardness of distribution-free learning: P/poly is not weakly PAC learnable on average by nonuniform 2^o(n/log n)-time algorithms. - Weak cryptographic primitives: There exist a hitting set generator, an auxiliary-input one-way function, an auxiliary-input pseudorandom generator, and an auxiliary-input pseudorandom function against SIZE^𝒪[2^o(n/log n)]. This provides considerable insights into Pessiland (i.e., the world in which no one-way function exists, and NP is hard on average), such as the relativized separation of the error-prone average-case hardness of NP and auxiliary-input cryptography. At the core of our oracle construction is a new notion of random restriction with masks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Hirahara and Mikito Nanashima 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.25 urn:nbn:de:0030-drops-165875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.25 eng https://creativecommons.org/licenses/by/4.0/legalcode