On characterizations of randomized computation using plain Kolmogorov complexity

DOI10.1007/978-3-662-44465-8_30MaRDI QIDQ2922621zbMATH OpenOpenAlexFDO

Authors Shuichi Hirahara, Akitoshi Kawamura

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44465-8_30

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Randomized algorithms (68W20)

Recommendations

• On characterizations of randomized computation using plain Kolmogorov complexity
• Limits on the Computational Power of Random Strings
• Limits on the computational power of random strings
• STACS 2004

Cited in

(4)

• An additivity theorem for plain Kolmogorov complexity
• The Complexity of Complexity
• scientific article; zbMATH DE number 2019634 (Why is no real title available?)
• On characterizations of randomized computation using plain Kolmogorov complexity

This page was built for publication: On characterizations of randomized computation using plain Kolmogorov complexity

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