Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds.
Eric Allender · 2008
Abstract. This invited Descriptional Complexity of Formal Systems lecture provides an opportunity to raise awareness of the tight connection that exists between Kolmogorov Complexity and Circuit Complexity, and to argue that this connection is useful and interesting. Kolmogorov complexity has been used to provide examples of complete sets for classes such as EXP and PSPACE that are fundamentally different than the usual complete sets (in the sense that they are provably not complete under the usual reducibilities). Furthermore, there are connections between Kolmogorov complexity and recent approaches to proving lower bounds on circuit size. Keywords: