DocumentCode
1683474
Title
Are Cook and Karp ever the same?
Author
Beigel, Richard ; Fortnow, Lance
Author_Institution
Dept. of Comput. & Inf. Sci., Temple Univ., Philadelphia, PA, USA
fYear
2003
Firstpage
333
Lastpage
336
Abstract
We consider the question whether there exists a set A such that every set polynomial-time Turing equivalent to A is also many-one equivalent to A. We show that if E=NE then no sparse set has this property. We give the first relativized world where there exists a set with this property, and in this world the set A is sparse.
Keywords
Turing machines; computational complexity; set theory; NP-completeness; many-one equivalent set; polynomial-time Turing equivalent; sparse set; Computational complexity; Laboratories; National electric code; Polynomials; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
ISSN
1093-0159
Print_ISBN
0-7695-1879-6
Type
conf
DOI
10.1109/CCC.2003.1214431
Filename
1214431
Link To Document