On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity

DOI10.1007/978-3-662-44465-8_30zbMath1390.68357OpenAlexW2273702009MaRDI QIDQ2922621

Akitoshi Kawamura, Shuichi Hirahara

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

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

Related Items (1)

The Complexity of Complexity

This page was built for publication: On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity