THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS
From MaRDI portal
Publication:3021962
DOI10.1142/S0129054102001199zbMath1066.68057OpenAlexW2148452608MaRDI QIDQ3021962
Publication date: 22 June 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054102001199
computational complexityalgorithmic information theoryKolmogorov complexityaccelerationBlum's speed-up theoremLevin search
Analysis of algorithms (68W40) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
ON OPTIMAL INVERTERS ⋮ Open problems in universal induction \& intelligence ⋮ On Universal Transfer Learning ⋮ On universal transfer learning ⋮ A theory of incremental compression ⋮ Consistency and Optimality
Cites Work
- A Mathematical Theory of Communication
- Relations between diagonalization, proof systems, and complexity gaps
- Gaussian elimination is not optimal
- Randomness conservation inequalities; information and independence in mathematical theories
- Complexity-based induction systems: Comparisons and convergence theorems
- Minimum description length induction, Bayesianism, and Kolmogorov complexity
- A Machine-Independent Theory of the Complexity of Recursive Functions
- On the Length of Programs for Computing Finite Binary Sequences
- On Effective Procedures for Speeding Up Algorithms
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- A formal theory of inductive inference. Part I
