Logics which capture complexity classes over the reals

DOI10.2307/2586770MaRDI QIDQ4254641zbMATH OpenOpenAlexFDO

Authors Felipe Cucker, Klaus Meer

Publication date 29 June 1999

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2586770

zbMATH Keywords

descriptive complexity theorylogical description of complexity classesreal number model of computation

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Logics which capture complexity classes over the reals
• scientific article; zbMATH DE number 2063216
• scientific article; zbMATH DE number 1263207
• scientific article; zbMATH DE number 953024
• scientific article; zbMATH DE number 1361497

Cited in

(16)

• Exotic quantifiers, complexity classes, and complete problems
• Counting problems over the reals
• Real computations with fake numbers
• A logical characterization of constant-depth circuits over the reals
• Periodic generalized automata over the reals
• Implicit complexity over an arbitrary structure: Quantifier alternations
• scientific article; zbMATH DE number 2063216 (Why is no real title available?)
• Logics for complexity classes
• scientific article; zbMATH DE number 953024 (Why is no real title available?)
• Metafinite model theory and real number computations
• Logics which capture complexity classes over the reals
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Logics capturing relativized complexity classes uniformly
• Logical characterizations of algebraic circuit classes over integral domains
• A logical characterization of constant-depth circuits over the reals

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254641)