Name
Abstract | ||
|---|---|---|
Mahaney's Theorem states that there are no sparse NP-complete problems if P not equal NP. We propose an adaptation of that theorem to the Blum-Shub-Smale model of computation of the reals with addition and equality. In that setting, sparseness is defined in terms of topological dimension instead of cardinality. (C) 1997 Elsevier Science B.V. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0020-0190(97)00060-4 | Inf. Process. Lett. |
Keywords | Field | DocType |
np complete problem,decision tree,model of computation,computational complexity | Decision tree,Discrete mathematics,NP-complete,Combinatorics,Lebesgue covering dimension,Cardinality,Model of computation,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
62 | 4 | 0020-0190 |
Citations | PageRank | References |
5 | 0.86 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Felipe Cucker | 1 | 666 | 68.99 |
| Pascal Koiran | 2 | 919 | 113.85 |
| Martín Matamala | 3 | 158 | 21.63 |