Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy

With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy

File(s)
85-715.pdf (1.11 MB)
85-715.ps (439.87 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6555
Collections
Computer Science Technical Reports
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
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-715
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance