[图书][B] An introduction to Kolmogorov complexity and its applications
Ming Li Paul Vitányi Fourth Edition Page 1 An Introduction to Kolmogorov Complexity and Its
Applications Ming Li Paul Vitányi Fourth Edition Texts in Computer Science Page 2 Texts in …
Applications Ming Li Paul Vitányi Fourth Edition Texts in Computer Science Page 2 Texts in …
Small progress measures for solving parity games
M Jurdziński - Annual Symposium on Theoretical Aspects of …, 2000 - Springer
In this paper we develop a new algorithm for deciding the winner in parity games, and hence
also for the modal μ-calculus model checking. The design and analysis of the algorithm is …
also for the modal μ-calculus model checking. The design and analysis of the algorithm is …
Power from random strings
We show that sets consisting of strings of high Kolmogorov complexity provide examples of
sets that are complete for several complexity classes under probabilistic and nonuniform …
sets that are complete for several complexity classes under probabilistic and nonuniform …
The quantitative structure of exponential time
JH Lutz - [1993] Proceedings of the Eigth Annual Structure in …, 1993 - ieeexplore.ieee.org
Recent results on the internal, measure-theoretic structure of the exponential time
complexity classes E= DTIME (2/sup linear/) and E/sub 2/= DTIME (2/sup polynomial/) are …
complexity classes E= DTIME (2/sup linear/) and E/sub 2/= DTIME (2/sup polynomial/) are …
Unexpected hardness results for Kolmogorov complexity under uniform reductions
S Hirahara - Proceedings of the 52nd Annual ACM SIGACT …, 2020 - dl.acm.org
Hardness of computing the Kolmogorov complexity of a given string is closely tied to a
security proof of hitting set generators, and thus understanding hardness of Kolmogorov …
security proof of hitting set generators, and thus understanding hardness of Kolmogorov …
[PDF][PDF] Symmetry of information from meta-complexity
S Hirahara - 37th Computational Complexity Conference (CCC …, 2022 - drops.dagstuhl.de
Symmetry of information for time-bounded Kolmogorov complexity is a hypothetical
inequality that relates time-bounded Kolmogorov complexity and its conditional analogue. In …
inequality that relates time-bounded Kolmogorov complexity and its conditional analogue. In …
Limits of minimum circuit size problem as oracle
S Hirahara, O Watanabe - 31st Conference on Computational …, 2016 - drops.dagstuhl.de
Abstract The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero
knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP …
knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP …
The complexity of complexity
E Allender - Computability and Complexity: Essays Dedicated to …, 2016 - Springer
The Complexity of Complexity | SpringerLink Skip to main content Advertisement SpringerLink
Account Menu Find a journal Publish with us Track your research Search Cart Book cover …
Account Menu Find a journal Publish with us Track your research Search Cart Book cover …
When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity
E Allender - FST TCS 2001: Foundations of Software Technology …, 2001 - Springer
This paper has the following goals: To survey some of the recent developments in the field of
derandomization. To introduce a new notion of time-bounded Kolmogorov complexity (KT) …
derandomization. To introduce a new notion of time-bounded Kolmogorov complexity (KT) …
On the complexity of random strings
M Kummer - Annual Symposium on Theoretical Aspects of …, 1996 - Springer
We show that the set R of Kolmogorov random strings is truth-table complete. This improves
the previously known Turing completeness of R and shows how the halting problem can be …
the previously known Turing completeness of R and shows how the halting problem can be …