License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2015.244
URN: urn:nbn:de:0030-drops-50718
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5071/
Go to the corresponding LIPIcs Volume Portal

Hirahara, Shuichi

Identifying an Honest EXP^NP Oracle Among Many

pdf-format:
23.pdf (0.5 MB)

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 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).

BibTeX - Entry

@InProceedings{hirahara:LIPIcs:2015:5071,
  author =	{Shuichi Hirahara},
  title =	{{Identifying an Honest EXP^NP Oracle Among Many}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{244--263},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5071},
  URN =		{urn:nbn:de:0030-drops-50718},
  doi =		{10.4230/LIPIcs.CCC.2015.244},
  annote =	{Keywords: nonuniform complexity, short advice, instance checker, interactive proof systems, probabilistic checkable proofs}
}

Keywords: nonuniform complexity, short advice, instance checker, interactive proof systems, probabilistic checkable proofs
Collection: 30th Conference on Computational Complexity (CCC 2015)
Issue Date: 2015
Date of publication: 06.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI