loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 IEEE 23rd Annual Conference on Computational Complexity
Amplifying ZPP^SAT[1] and the Two Queries Problem
June 22-June 26
ISBN: 978-0-7695-3169-4
This paper shows a complete upward collapse in the Polynomial Hierarchy (PH) if for ZPP, two queries to a SAT oracle is equivalent to one query. That is, ZPP^SAT[1] = ZPP^SAT||[2] implies ZPP^SAT[1] = PH. Here, the ZPP machines are required to succeed with probability at least 1/2 + 1/p(n) on inputs of length n for some polynomial p(n). This result builds upon recent work by Tripathi who showed a collapse of PH to S_2^P. The use of the probability bound of 1/2 + 1/p(n) is justified in part by showing that this bound can be amplified to 1 - 2^{-n^k} for ZPP^SAT[1] computations. This paper also shows that in the deterministic case, P^SAT[1] = P^SAT||[2] implies PH is contained in ZPP^SAT[1] where the ZPP^SAT[1] machine achieves a probability of success of 1/2 - 2^{-n^k}.
Index Terms:
ZPP, bounded queries, amplification
Citation:
Richard Chang, Suresh Purini, "Amplifying ZPP^SAT[1] and the Two Queries Problem," ccc, pp.41-52, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.