On characterizations of randomized computation using plain Kolmogorov complexity

DOI10.3233/COM-170075zbMATH Open1390.68358MaRDI QIDQ4608445FDOQ4608445

Authors: Shuichi Hirahara, Akitoshi Kawamura 

Publication date: 16 March 2018

Published in: Computability (Search for Journal in Brave)

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
• Reductions to the set of random strings: the resource-bounded case

zbMATH Keywords

Kolmogorov complexityrandomnesstruth-table reductions

Mathematics Subject Classification ID

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

Cited In (2)

• An additivity theorem for plain Kolmogorov complexity
• Title not available (Why is that?)

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 Q4608445)