2026-07-23T00:29:27Z https://drops.dagstuhl.de/oai

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

Errorless Versus Error-Prone Average-Case Complexity Hirahara, Shuichi Santhanam, Rahul average-case complexity instance checker pseudorandomness We consider the question of whether errorless and error-prone notions of average-case hardness are equivalent, and make several contributions. First, we study this question in the context of hardness for NP, and connect it to the long-standing open question of whether there are instance checkers for NP. We show that there is an efficient non-uniform non-adaptive reduction from errorless to error-prone heuristics for NP if and only if there is an efficient non-uniform average-case non-adaptive instance-checker for NP. We also suggest an approach to proving equivalence of the two notions of average-case hardness for PH. Second, we show unconditionally that error-prone average-case hardness is equivalent to errorless average-case hardness for P against NC¹ and for UP ∩ coUP against P. Third, we apply our results about errorless and error-prone average-case hardness to get new equivalences between hitting set generators and pseudo-random 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.84 urn:nbn:de:0030-drops-156803 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.84 eng https://creativecommons.org/licenses/by/4.0/legalcode