Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6555
 Title: With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy Authors: Cai, Jin-yi Keywords: computer sciencetechnical report Issue Date: Dec-1985 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-715 Abstract: We consider how much error a fixed depth Boolean circuit has to make for computing the parity function. We show that with an exponential bound of the form $exp(n^{\lambda})$ on the size of the circuits, they make asymptotically 50% error on all possible input, uniformly. As a consequence, we show that with a random oracle set $A,Pr.(PSPACE^{A} \supseteq PH^{A} = 1$. URI: http://hdl.handle.net/1813/6555 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat