On Kolmogorov complexity in the real Turing machine setting
From MaRDI portal
Publication:293323
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
Kolmogorov complexityalgebaric complexity theoryreal computationreal Turing machinesstraight-line complexity
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: On Kolmogorov complexity in the real Turing machine setting
