DocumentCode
2177380
Title
A second step toward the polynomial hierarchy
Author
Baker, Theodore P. ; Selman, Alan L.
fYear
1976
fDate
25-27 Oct. 1976
Firstpage
71
Lastpage
75
Abstract
Some of the questions posed by Baker, Gill, and Solovay [1] are here answered. The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ2P,B ≠ π2P,B. It follows that Σ2P,B ⊂≠ Σ3P,B.
Keywords
Arithmetic; Concrete; Humans; Mathematics; Polynomials; Visualization;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1976., 17th Annual Symposium on
Conference_Location
Houston, TX, USA
ISSN
0272-5428
Type
conf
DOI
10.1109/SFCS.1976.2
Filename
4567889
Link To Document