With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy
Permanent Link(s)
Collections
Author
Cai, Jin-yi
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$.
Date Issued
1985-12
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-715
Type
technical report