Department of
Applied
Mathematics

New Chapters in an Old Story: Circuit Size Minimization and Kolmogorov Complexity

Eric Allender

Rutgers

Abstract

The Minimum Circuit Size Problem (MCSP) has received a great deal of attention from complexity theoreticians over the years, and yet very little is known about its complexity. It is frequently mentioned as a candidate for "NP intermediate" status (i.e., not being NP-complete, but also not being in P), and indeed there is a great deal of evidence that MCSP is not in P, but there is not much firm evidence against it being NP-complete. Several papers studying MCSP have found it convenient to study a problem related to time-bounded Kolmogorov complexity (MKTP) as a tool for understanding MCSP. Initially, it seemed that every theorem that one could prove about MKTP applied equally well to MCSP, and vice-versa.

Recently, a new and simple approach was developed that allows us to prove several theorems about MKTP that are not yet known to hold for MCSP. For example, we can show:

* MKTP does not lie in the circuit complexity class AC^0[p] for any prime p.

* MKTP is hard for an important subclass of NP (including the Graph Isomorphism problem) under zero-error probabilistic reductions.

* Certain longstanding questions in circuit complexity are equivalent to questions about what can be reduced to MKTP under restrictive reductions.

None of these are known to be true for MCSP.

This is joint work from papers of the speaker with Shuichi Hirahara and with Josh Grochow, Dieter van Melkebeek, Chris Moore, and Andrew Morgan.