Name
Abstract | ||
|---|---|---|
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 EXPNP-complete languages exists unless EXPNP = NEXP, we prove that there exists a selector for any EXPNP-complete language, by building on the proof of MIP = NEXP by Babai, Fortnow, and Lund (1991). |
Year | Venue | DocType |
|---|---|---|
2015 | Conference on Computational Complexity | Journal |
Volume | Citations | PageRank |
abs/1502.07258 | 0 | 0.34 |
References | Authors | |
11 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shuichi Hirahara | 1 | 3 | 7.48 |