On characterizations of randomized computation using plain Kolmogorov complexity1

DOI10.3233/COM-170075zbMath1390.68358MaRDI QIDQ4608445

Akitoshi Kawamura, Shuichi Hirahara

Publication date: 16 March 2018

Published in: Computability (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexity; randomness; truth-table reductions

Mathematics Subject Classification ID

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68W20: Randomized algorithms