2026-07-23T08:35:19Z https://drops.dagstuhl.de/oai

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

Excluding PH Pessiland Hirahara, Shuichi Santhanam, Rahul average-case complexity pseudorandomness meta-complexity Heuristica and Pessiland are "worlds" of average-case complexity [Impagliazzo95] that are considered unlikely but that current techniques are unable to rule out. Recently, [Hirahara20] considered a PH (Polynomial Hierarchy) analogue of Heuristica, and showed that to rule it out, it would be sufficient to prove the NP-completeness of the problem GapMINKT^PH of estimating the PH-oracle time-bounded Kolmogorov complexity of a string. In this work, we analogously define "PH Pessiland" to be a world where PH is hard on average but PH-computable pseudo-random generators do not exist. We unconditionally rule out PH-Pessiland in both non-uniform and uniform settings, by showing that the distributional problem of computing PH-oracle time-bounded Kolmogorov complexity of a string over the uniform distribution is complete for an (error-prone) average-case analogue of PH. Moreover, we show the equivalence between error-prone average-case hardness of PH and the existence of PH-computable pseudorandom generators. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Hirahara and Rahul Santhanam 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.85 urn:nbn:de:0030-drops-156819 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.85 eng https://creativecommons.org/licenses/by/4.0/legalcode