Learning from bounded arithmetic

Abstract: The central question of complexity theory -- what can (and cannot) be feasibly computed -- has a corresponding logical meta-question: what can (and cannot) be feasibly proven. While complexity theory studies the former, bounded arithmetic is one of the main approaches to the meta-question. There is a tight relation between theories of bounded arithmetic and corresponding complexity classes, allowing one to study what can be proven in, for example, "polynomial-time reasoning" and what power is needed to resolve complexity questions, with a number of both positive and negative provability results.

Here, we focus on the complexity of another meta-problem: learning to solve problems such as Boolean satisfiability. There is a range of ways to define "solving problems", with one extreme, the uniform setting, being an existence of a fast algorithm (potentially randomized), and another of a potentially non-computable family of small Boolean circuits, one for each problem size. The complexity of learning can be recast as the complexity of finding a procedure to generate Boolean circuits solving the problem of a given size, if it (and such a family of circuits) exists.

First, inspired by the KPT witnessing theorem, a special case of Herbrand's theorem in bounded arithmetic, we develop an intermediate notion of uniformity that we call LEARN-uniformity. While non-uniform lower bounds are notoriously difficult, we can prove several unconditional lower bounds for this weaker notion of uniformity. Then, returning to the world of bounded arithmetic and using that notion of uniformity as a tool, we show unprovability of several complexity upper bounds for both deterministic and randomized complexity classes, in particular giving simpler proofs that the theory of polynomial-time reasoning PV does not prove that all of P is computable by circuits of a specific polynomial size, and the theory $V^1$, a second-order counterpart to the classic Buss' theory $S^1_2$, does not prove the same statement with NP instead of P.

Finally, we leverage these ideas to show that bounded arithmetic "has trouble differentiating" between uniform and non-uniform frameworks: more specifically, we show that theories for polynomial-time and randomized polynomial-time reasoning cannot prove both a uniform lower bound and a non-uniform upper bound for NP. In particular, while it is possible that NP != P yet all of NP is computable by families of polynomial-size circuits, this cannot be proven feasibly.

computational complexitymachine learninglogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic