## N.Thapen's lecture at the

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.

Fall school (Sept.'11)

The provably total NP search problems

of weak second order bounded arithmetic