On the computational structure of the connected components of a hard problem
From MaRDI portal
Publication:1607000
DOI10.1016/S0020-0190(99)00130-1zbMath0999.68075OpenAlexW2071776137MaRDI QIDQ1607000
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00130-1
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity and dimension
- A low and a high hierarchy within NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On sparse sets in NP-P
- A note on a \(P \neq NP\) result for a restricted class of real machines
- A survey on real structural complexity theory
- Computing over the reals with addition and order
- On the complexity of quadratic programming in real number models of computation
- On NP-completeness for linear machines
- Computing over the reals with addition and order: Higher complexity classes
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the Relations Between Discrete and Continuous Complexity Theory
- Bounds for the computational power and learning complexity of analog neural nets
