On Ladner's result for a class of real machines with restricted use of constants
From MaRDI portal
Publication:418114
DOI10.1016/j.ic.2011.11.001zbMath1280.68101OpenAlexW2077424813MaRDI QIDQ418114
Publication date: 24 May 2012
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.11.001
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Exotic quantifiers, complexity classes, and complete problems
- Saturation and stability in the theory of computation over the reals
- Separation of complexity classes in Koiran's weak model
- P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
- A note on non-complete problems in \(NP_\mathbb{R}\)
- On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants
- On the Structure of Polynomial Time Reducibility
- On the Structure of $\cal NP_\Bbb C$
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO