Document Type

Report

Date

6-20-1990

Embargo Period

5-1-2012

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.

Additional Information

School of Computer and Information Science, Syracuse University SU-CIS-90-17

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.