Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

Authors :: Eric Allender
Source :: New Zealand Journal of Mathematics. 52:585-604
Publication Year :: 2021
Publisher :: New Zealand Journal of Mathematics Committee, 2021.
Abstract: We survey recent developments related to the Minimum Circuit Size Problem and time-bounded Kolmogorov Complexity.

Subjects :: Algebra and Number Theory
Kolmogorov complexity
Computer science
Applied Mathematics
Applied mathematics
Geometry and Topology
Circuit minimization for Boolean functions
Analysis

Full Text Access

Tools