Complexity and dimension
DOI10.1016/S0020-0190(97)00060-4zbMATH Open1337.68117OpenAlexW1976838138MaRDI QIDQ287068FDOQ287068
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
Recommendations
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)
Cites Work
- 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
- 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
Cited In (12)
- Complexity and heights of tori
- Complexity in the presence of a boundary
- On the computational structure of the connected components of a hard problem
- On sparseness and Turing reducibility over the reals
- Complexity and the bulk volume, a New York time story
- Sparse NP-complete problems over the reals with addition
- On sparseness, reducibilities, and complexity
- Title not available (Why is that?)
- Complexity with Rod
- Title not available (Why is that?)
- On weak-space complexity over complex numbers
- Complexity and behind the horizon cut off
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)
