N.Thapen's lecture at the
Fall school (Sept.'11)

The provably total NP search problems
of weak second order bounded arithmetic

---

I will talk about some work analyzing the strength of bounded arithmetic theories through characterizing the NP search problems that they prove are total. In particular I will describe a new family of principles about labellings of large, bounded degree graphs which characterize the search problems for a range of first-order and weak second-order bounded arithmetic theories, in this way capturing the low-complexity consequences of some rather strong theories.