Complexity Approximation Principle

DOI10.1093/COMJNL/42.4.318MaRDI QIDQ4933950zbMATH OpenOpenAlexFDO

Authors Alexander Gammerman, Vladimir Vovk

Publication date 17 January 2000

Published in The Computer Journal (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/4a8a8a5dfe48874f05ad9cc2f06a4a2f0da13099

zbMATH Keywords

complexity approximation principleKolmogorov complexityminimum description lengthminimum message length

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Complexity of approximation problems
• scientific article; zbMATH DE number 3999286
• scientific article; zbMATH DE number 4057841
• scientific article; zbMATH DE number 1206797
• Approximating Kolmogorov complexity
• Approximability and proof complexity
• The complexity of polynomial-time approximation
• On the approximation complexity hierarchy
• scientific article; zbMATH DE number 7301304
• scientific article; zbMATH DE number 2212170

Cited in

(10)

• Does snooping help?
• Predictive complexity and information
• Most sequences are stochastic
• Suboptimal measures of predictive complexity for absolute loss function
• On complexity of easy predictable sequences
• scientific article; zbMATH DE number 14502 (Why is no real title available?)
• Competitive On-line Statistics
• Explanatory and creative alternatives to the MDL principle
• General linear relations between different types of predictive complexity
• Most relevant explanation: Computational complexity and approximation methods

This page was built for publication: Complexity Approximation Principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933950)