loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th Annual IEEE Conference on Computational Complexity (CCC'03)
Are Cook and Karp Ever the Same?
Aarhus, Denmark
July 07-July 10
ISBN: 0-7695-1879-6
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.