On sparseness, reducibilities, and complexity

DOI10.1016/j.apal.2004.06.011zbMath1085.03029OpenAlexW2013347233WikidataQ57733218 ScholiaQ57733218MaRDI QIDQ1779309

Felipe Cucker

Publication date: 1 June 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.06.011

zbMATH Keywords

sparse setscompleteness over the realscomputation over the realsreducibilities over the reals

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• A note on a \(P \neq NP\) result for a restricted class of real machines
• On log-tape isomorphisms of complete sets
• 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, reducibilities, and complexity