Finding Errorless Pessiland in Error-Prone Heuristica

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