Title :
On separating complexity classes
Author_Institution :
Dept. of Math., California Univ., Santa Barbara, CA, USA
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113978