2026-07-24T00:02:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5071 2024-03-06T10:35:46Z ddc:004 open_access

Identifying an Honest EXP^NP Oracle Among Many Hirahara, Shuichi nonuniform complexity short advice instance checker interactive proof systems probabilistic checkable proofs We provide a general framework to remove short advice by formulating the following computational task for a function f: given two oracles at least one of which is honest (i.e. correctly computes f on all inputs) as well as an input, the task is to compute f on the input with the help of the oracles by a probabilistic polynomial-time machine, which we shall call a selector. We characterize the languages for which short advice can be removed by the notion of selector: a paddable language has a selector if and only if short advice of a probabilistic machine that accepts the language can be removed under any relativized world. Previously, instance checkers have served as a useful tool to remove short advice of probabilistic computation. We indicate that existence of instance checkers is a property stronger than that of removing short advice: although no instance checker for EXP^NP-complete languages exists unless EXP^NP = NEXP, we prove that there exists a selector for any EXP^NP-complete language, by building on the proof of MIP = NEXP by Babai, Fortnow, and Lund (1991). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Hirahara 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.244 urn:nbn:de:0030-drops-50718 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.244 eng https://creativecommons.org/licenses/by/3.0/legalcode