COMPLEXITY AND DIMENSION

Authors
CUCKER F KOIRAN P MATAMALA M
Citation
F. Cucker et al., COMPLEXITY AND DIMENSION, Information processing letters, 62(4), 1997, pp. 209-212
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
62
Issue
4
Year of publication
1997
Pages
209 - 212
Database
ISI
SICI code
0020-0190(1997)62:4<209:CAD>2.0.ZU;2-3
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 Bl um-Shub-Smale model of computation of the reals with addition and equa lity. In that setting, sparseness is defined in terms of topological d imension instead of cardinality. (C) 1997 Elsevier Science B.V.