On sparseness and Turing reducibility over the reals

DOI10.1016/S1571-0661(04)80537-1zbMath1261.03135DBLPjournals/entcs/Cucker02OpenAlexW2081323336WikidataQ57733262 ScholiaQ57733262MaRDI QIDQ4916198

Felipe Cucker

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

zbMATH Keywords

Turing reducibilityreal computationsparseness

Mathematics Subject Classification ID

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 NP_w-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