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
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;
Conference_Titel :
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
Print_ISBN :
0-7695-1879-6
DOI :
10.1109/CCC.2003.1214431
