Name
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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/CCC.2003.1214431 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
turing machines,polynomials,national electric code,set theory,computational complexity,np completeness,polynomial time | 2-EXPTIME,Set theory,Discrete mathematics,Sparse language,Hyperarithmetical theory,Turing degree,Turing reduction,Turing machine,Time hierarchy theorem,Mathematics | Conference |
ISSN | Citations | PageRank |
1093-0159 | 3 | 0.35 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard Beigel | 1 | 247 | 28.41 |
| Lance Fortnow | 2 | 2788 | 352.32 |