Kolmogorov Complexity Theory over the Reals

DOI10.1016/j.entcs.2008.12.014zbMath1262.68057OpenAlexW2167816279MaRDI QIDQ4918012

Wouter M. Koolen, Martin Ziegler

Publication date: 3 May 2013

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2008.12.014

zbMATH Keywords

Kolmogorov complexitytranscendence degreeBSS modelreal recursion theory

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computation over the reals, computable analysis (03D78)

Related Items

On the Kolmogorov Complexity of Continuous Real Functions

Cites Work

• On Kolmogorov complexity in the real Turing machine setting
• VPSPACE and a transfer theorem over the reals
• A survey on real structural complexity theory
• Analytic machines
• Completeness and reduction in algebraic complexity theory
• Counting problems over the reals
• Isomorphism theorem for BSS recursively enumerable sets over real closed fields
• Computing over the reals with addition and order: Higher complexity classes
• Cook's versus Valiant's hypothesis
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
• On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds
• The Arithmetical Hierarchy Over the Reals
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Fundamentals of Computation Theory
• Algorithms in real algebraic geometry
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item