Complexity and dimension

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

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

algebraic decision treescomputational complexitysparse sets

Mathematics Subject Classification ID

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

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 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 a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On Isomorphisms and Density of NP and Other Complete Sets
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis

Cited in

(13)

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

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)