On sparseness, reducibilities, and complexity
From MaRDI portal
Publication:1779309
DOI10.1016/j.apal.2004.06.011zbMath1085.03029OpenAlexW2013347233WikidataQ57733218 ScholiaQ57733218MaRDI QIDQ1779309
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
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 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, reducibilities, and complexity