Complexity and dimension
From MaRDI portal
Publication:287068
DOI10.1016/S0020-0190(97)00060-4zbMath1337.68117OpenAlexW1976838138MaRDI QIDQ287068
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
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computation over the reals, computable analysis (03D78)
Related Items
On sparseness and Turing reducibility over the reals ⋮ Sparse NP-complete problems over the reals with addition ⋮ On sparseness, reducibilities, and complexity ⋮ On the computational structure of the connected components of a hard problem
Cites Work
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- 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
