On Ladner's result for a class of real machines with restricted use of constants

DOI10.1016/j.ic.2011.11.001zbMath1280.68101OpenAlexW2077424813MaRDI QIDQ418114

Klaus Meer

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

zbMATH Keywords

complexitydiagonal problemsLadner's theoremreal number model

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)

Related Items

A Survey on Analog Models of Computation

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