Title: Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic
Speaker: Eric Allender, Rutgers University
Date: Wednesday, January 25, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems C defined in terms of polynomial-time truth-table reducibility to R_K (the set of Kolmogorov-random strings) that lies between BPP and PSPACE. In this talk, we investigate improving this upper bound from PSPACE to [PSPACE intersect P/poly]. (P/poly is the class of problems with polynomial-size circuits.)
More precisely, we present a collection of true statements in the language of arithmetic, (each provable in ZF) and show that if these statements can be proved in certain extensions of Peano arithmetic, then BPP \subseteq C \subseteq PSPACE intersect P/poly.
We conjecture that C is equal to P, and discuss the possibility this might be an avenue for trying to prove the equality of BPP and P.
Joint work with George Davie, Luke Friedman, Sam Hopkins, and Iddo Tzameret.