DocumentCode :
2722503
Title :
On separating complexity classes
Author :
Book, Ronald V.
Author_Institution :
Dept. of Math., California Univ., Santa Barbara, CA, USA
fYear :
1990
fDate :
8-11 July 1990
Firstpage :
299
Lastpage :
304
Abstract :
Some observations that suggest that certain separation results based on the use of random oracles will not provide information about the separation of the corresponding unrelativized classes (without some additional hypothesis) are presented. It is observed that J.-Y Cai´s (1989) result showing that for almost every set A, PH(A)≠PSPACE(A), does not address the open question of whether PH is equal to PSPACE. In addition, it is observed that D. Bennett and J. Gill´s (1981) result that for almost every set A, P(A)≠NP(A) does not address the open questions of whether P is equal to NP or whether BPP is equal to AM
Keywords :
Turing machines; computational complexity; AM; BPP; NP; PH; PSPACE; Turing machines; complexity classes; random oracles; separation; unrelativized classes; Books; Mathematics;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
Type :
conf
DOI :
10.1109/SCT.1990.113978
Filename :
113978
Link To Document :
بازگشت