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 theoryreal number model of computationlogical description of complexity classes

Mathematics Subject Classification ID

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

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

(14)

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

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)