loading...
Are Cook and Karp Ever the Same?
Aarhus, Denmark July 07-July 10
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.121443118th Annual IEEE Conference on Comput ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Richard Beigel, Lance Fortnow, "Are Cook and Karp Ever the Same?," Computational Complexity, Annual IEEE Conference on, pp. 333, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2003.1214431,
author = {Richard Beigel and Lance Fortnow},
title = {Are Cook and Karp Ever the Same?},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2003},
issn = {1093-0159},
pages = {333},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214431},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Are Cook and Karp Ever the Same?
SN - 1093-0159
SP
EP
A1 - Richard Beigel,
A1 - Lance Fortnow,
PY - 2003
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Richard Beigel, Temple University
Lance Fortnow, NEC Laboratories America
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.
Citation:
Richard Beigel, Lance Fortnow, "Are Cook and Karp Ever the Same?," ccc, pp.333, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.