Document Type
Report
Date
6-20-1990
Keywords
Computational complexity, theory of computation, polynomial-time hierarchy, randomness, oracles.
Language
English
Disciplines
Computer Sciences
Description/Abstract
We simplify the proof by S. Toda [Tod89] that the polynomial hierarchy PH is contained in BP[ӨP]. Our methods bypass the technical quantifier interchange lemmas in the original proof, and clarify the counting principles on which the result depends. We also show that relative to a random oracle R, PHR is strictly contained in ӨPR.
Recommended Citation
Regan, Kenneth W. and Royer, James S., "A Simpler Proof of PH C BP[ӨP]" (1990). Electrical Engineering and Computer Science - Technical Reports. 96.
https://surface.syr.edu/eecs_techreports/96
Source
local
Additional Information
School of Computer and Information Science, Syracuse University SU-CIS-90-17