Seminários de Lógica Matemática

5 de Fevereiro 2009, 18h00

The model-theoretic proof of the witnessing theorem of bounded arithmetic (an exposition)
Complexo Interdisciplinar, Sala B3-01

KERRY OJAKIAN (SQIG-IT)

Abstract:

I will introduce the framework of Bounded Arithmetic (BA), a subtheory of Peano Arithmetic which corresponds to "polynomial-time reasoning." One of the key facts about BA is the polynomial-time witnessing theorem, which says that the provably- total functions of BA are exactly the polynomial-time functions. The original proof of this fact was proof theoretic. Subsequently there were model theoretic proofs, one from Wilkie (written up by Hajek and Pudlak) and one from Zambella. I will give an exposition of Zambella ´s proof. I will only assume knowledge of basic logic, basic model theory, and very basic computational complexity theory.

| back