On characterizations of randomized computation using plain Kolmogorov complexity1
From MaRDI portal
Publication:4608445
DOI10.3233/COM-170075zbMath1390.68358MaRDI QIDQ4608445
Akitoshi Kawamura, Shuichi Hirahara
Publication date: 16 March 2018
Published in: Computability (Search for Journal in Brave)
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)