Document Open Access Logo

Identifying an Honest EXP^NP Oracle Among Many

Author Shuichi Hirahara

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.244.pdf
  • Filesize: 0.53 MB
  • 20 pages

Document Identifiers

Author Details

Shuichi Hirahara

Cite As Get BibTex

Shuichi Hirahara. Identifying an Honest EXP^NP Oracle Among Many. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 244-263, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.244

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

Subject Classification

Keywords
  • nonuniform complexity
  • short advice
  • instance checker
  • interactive proof systems
  • probabilistic checkable proofs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1-2:54, 2009. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 1st edition, 2009. Google Scholar
  3. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. Google Scholar
  4. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. Google Scholar
  5. László Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC'91, pages 21-32, 1991. Google Scholar
  6. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex., 1:3-40, 1991. Google Scholar
  7. Boaz Barak. A probabilistic-time hierarchy theorem for "slightly non-uniform" algorithms. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, RANDOM'02, pages 194-208, 2002. Google Scholar
  8. Donald Beaver and Joan Feigenbaum. Hiding instances in multioracle queries. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, STACS'90, pages 37-48, 1990. Google Scholar
  9. Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM J. Comput., 38(2):551-607, 2008. Google Scholar
  10. Manuel Blum and Sampath Kannan. Designing programs that check their work. J. ACM, 42(1):269-291, 1995. Google Scholar
  11. Harry Buhrman, Lance Fortnow, Michal Koucký, and Bruno Loff. Derandomizing from random strings. In Proceedings of the 25th Annual Conference on Computational Complexity, CCC'10, pages 58-63, 2010. Google Scholar
  12. Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional lower bounds against advice. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, ICALP'09, pages 195-209, 2009. Google Scholar
  13. Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'92, pages 116-127, 1992. Google Scholar
  14. Jin-Yi Cai. S₂^p ⊆ ZPP^NP. J. Comput. Syst. Sci., 73(1):25-35, 2007. Google Scholar
  15. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268-292, 1996. Google Scholar
  16. Lance Fortnow and Adam Klivans. NP with small advice. In Proceedings of the 20th Annual Conference on Computational Complexity, CCC'05, pages 228-234, 2005. Google Scholar
  17. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. Theor. Comput. Sci., 134(2):545-557, 1994. Google Scholar
  18. Richard Karp and Richard Lipton. Turing machines that take advice. Enseign. Math, 28(2):191-209, 1982. Google Scholar
  19. Adam Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. Google Scholar
  20. Mark Krentel. The complexity of optimization problems. J. Comput. Syst. Sci., 36(3):490-509, 1988. Google Scholar
  21. Richard Lipton. New directions in testing. In Joan Feigenbaum and Michael Merritt, editors, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 2, pages 191-202. American Mathematical Society, 1991. Google Scholar
  22. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, 1992. Google Scholar
  23. Alexander Russell and Ravi Sundaram. Symmetric alternation captures BPP. Comput. Complex., 7(2):152-162, 1998. Google Scholar
  24. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. Google Scholar
  25. Luca Trevisan and Salil Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Comput. Complex., 16(4):331-364, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact