On sparseness and Turing reducibility over the reals
From MaRDI portal
Publication:4916198
DOI10.1016/S1571-0661(04)80537-1zbMath1261.03135DBLPjournals/entcs/Cucker02OpenAlexW2081323336WikidataQ57733262 ScholiaQ57733262MaRDI QIDQ4916198
Publication date: 19 April 2013
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s1571-0661(04)80537-1
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78)
Cites Work
- Unnamed Item
- Unnamed Item
- Complexity and dimension
- \(p\)-adic and real subanalytic sets
- A weak version of the Blum, Shub, and Smale model
- 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
- Separation of complexity classes in Koiran's weak model
- Geometric categories and o-minimal structures
- A theorem of the complement and some new o-minimal structures
- There are No Sparse NPw-Hard Sets
- 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 NP-complete problems over the reals with addition
This page was built for publication: On sparseness and Turing reducibility over the reals
