On zero error algorithms having oracle access to one query

Jin-Yi Cai () and Venkatesan T. Chakaravarthy ()
Additional contact information
Jin-Yi Cai: University of Wisconsin
Venkatesan T. Chakaravarthy: IBM India Research Lab

Journal of Combinatorial Optimization, 2006, vol. 11, issue 2, No 6, 189-202

Abstract: Abstract It is known that $${\rm S}_{2}^{p} \subseteq {\rm ZPP}^{NP}$$ (Cai, 2001). The reverse direction of whether ZPPNP is contained in $${\rm S}_{2}^{p}$$ remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and random string), then it can be simulated in $${\rm S}_{2}^{p}$$ . That is, we prove that $${\rm S}_{2}^{p}$$ . Next we consider whether the above result can be improved as $${\rm ZPP}^{NP[1]} \subseteq {\rm P}^{NP}$$ and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPPNP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ PNP, settling a long standing open problem. We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely, we prove that $${\rm ZPP}^{\Sigma_{2}^{p}[1]} \subseteq {\rm P}^{\Sigma_{2}^{p}[2]}$$ . On the other hand, by adapting our proof of our main result it can be shown that $${\rm ZPP}^{\Sigma_{2}^{p}[1]} \subseteq {\rm S}_{2}^{\rm NP[1]}$$ . For the purpose of comparing these two results, we prove that $${\rm P}^{\Sigma_{2}^{p}} \subseteq {\rm S}_{2}^{\rm NP[1]}$$ . We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2, $${\rm ZPP}^{\Sigma_{k}^{p}[1]} \subseteq {\rm P}^{\Sigma_{k}^{p}[2]}$$ and $${\rm P}^{\Sigma_{k}^{p}} \subseteq {\rm S}_{2}^{\Sigma_{k-1}^{p}[1]}$$ .

Keywords: Mathematical Modeling; Reverse Direction; Open Problem; Polynomial Time; Industrial Mathematic (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-7130-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:11:y:2006:i:2:d:10.1007_s10878-006-7130-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-7130-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().