On Kolmogorov complexity in the real Turing machine setting

DOI10.1016/S0020-0190(98)00089-1zbMath1338.68129MaRDI QIDQ293323

José Luis Montaña, Luis Miguel Pardo

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000891?np=y

zbMATH Keywords

Kolmogorov complexityalgebaric complexity theoryreal computationreal Turing machinesstraight-line complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)

Related Items (3)

Kolmogorov Complexity Theory over the Reals ⋮ Smale’s 17th problem: Average polynomial time to compute affine and projective solutions ⋮ On the Kolmogorov Complexity of Continuous Real Functions

Cites Work

• Lower bounds in algebraic computational complexity
• Some polynomials that are hard to compute
• Lower bounds for polynomials with algebraic coefficients
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• On the intrinsic complexity of elimination theory
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Polynomials with Rational Coefficients Which are Hard to Compute
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On Kolmogorov complexity in the real Turing machine setting