𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity and dimension

✍ Scribed by Felipe Cucker; Pascal Koiran; Martín Matamala

Book ID
104137395
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
313 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Mahaney's Theorem states that there are no sparse NP-complete problems if P # 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. @ 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

Dimension in Complexity Classes
Dimension in Complexity Classes
✍ Lutz, Jack H. 📂 Article 📅 2003 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 245 KB
G-Dimension, Complete Intersection Dimen
G-Dimension, Complete Intersection Dimension, Complexity, and Relative Homological Algebra
✍ Alex Martsinkovsky 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 112 KB

It is shown that the G-dimension and the complete intersection dimension are relative projective dimensions. Relative Auslander-Buchsbaum formulas are discussed. New cohomology theories, called complexity cohomology, are constructed. The new theories play the same role in identifying rings (and modu