DocumentCode
2722472
Title
A note on relativizing complexity classes with tally
Author
Hemachandra, Lane A. ; Rubinstein, Roy S.
Author_Institution
Dept. of Comput. Sci., Rochester Univ., NY, USA
fYear
1990
fDate
8-11 July 1990
Firstpage
287
Lastpage
294
Abstract
T. Long and A. Selman (1986) proved that, for most familiar pairs of complexity classes, separating the classes with a tally oracle is no easier than truly separating the classes. For relativized worlds, it is shown in this work that even for such pairs of classes, collapsing the classes with a tally oracle is easier than truly collapsing the classes, and it is demonstrated for the first time that for many familiar pairs of complexity classes, separating the classes with a tally oracle is easier than truly separating the classes
Keywords
computational complexity; NP completeness; relativizing complexity classes; tally; Books; Computer science; Displays; Error correction; Polynomials;
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.113976
Filename
113976
Link To Document