Complexity and dimension

DOI10.1016/S0020-0190(97)00060-4MaRDI QIDQ287068zbMATHOpenAlexFDO

Authors Felipe Cucker, Pascal Koiran, Martin Matamala

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00060-4

zbMATH Keywords

computational complexitysparse setsalgebraic decision trees

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computation over the reals, computable analysis (03D78) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On sparseness, reducibilities, and complexity
• Sparse NP-complete problems over the reals with addition
• On the computational structure of the connected components of a hard problem
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
• A note on a theorem of Blum, Shub, and Smale

Cites work

• A note on a \(P \neq NP\) result for a restricted class of real machines
• Computing over the reals with addition and order
• Computing over the reals with addition and order: Higher complexity classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis

Cited in

(12)

• Complexity and the bulk volume, a New York time story
• scientific article; zbMATH DE number 4090803 (Why is no real title available?)
• Complexity with Rod
• scientific article; zbMATH DE number 896399 (Why is no real title available?)
• Complexity in the presence of a boundary
• On weak-space complexity over complex numbers
• On sparseness and Turing reducibility over the reals
• Complexity and heights of tori
• Complexity and behind the horizon cut off
• On the computational structure of the connected components of a hard problem
• Sparse NP-complete problems over the reals with addition
• On sparseness, reducibilities, and complexity

This page was built for publication: Complexity and dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287068)