DocumentCode
2722420
Title
Impossibilities and possibilities of weak separation between NP and exponential time
Author
Lischke, Gerhard
Author_Institution
Dept. of Math., Friedrich-Schiller Univ., Jena, East Germany
fYear
1990
fDate
8-11 July 1990
Firstpage
245
Lastpage
253
Abstract
Two complexity classes are considered to be weakly separated if they are separated but there is no immune set in the difference of the classes. It is shown that the weak separation between NP and exponential time, together with the inclusion and the weak separation simultaneously in both directions (weak incomparability), is not possible in any relativized or nonrelativized world. On the other hand, a weak separation without inclusion and a strong-weak incomparability are realizable in relativized worlds
Keywords
computational complexity; NP; complexity classes; exponential time; weak incomparability; weak separation; Books; Computer science; Mathematics; Polynomials; Terminology; Turing machines; Writing;
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.113973
Filename
113973
Link To Document