Logics which capture complexity classes over the reals

DOI10.1007/BFB0036180OpenAlexW1568612680WikidataQ57733288 ScholiaQ57733288MaRDI QIDQ5055931

Felipe Cucker, Klaus Meer

Publication date: 9 December 2022

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0036180

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Computation over the reals, computable analysis (03D78)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Two \(P\)-complete problems in the theory of the reals
• A survey on real structural complexity theory
• On the complexity of quadratic programming in real number models of computation
• Metafinite model theory
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• On Relating Time and Space to Size and Depth
• On digital nondeterminism
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: Logics which capture complexity classes over the reals