Learning Bounded Arithmetic -- A Guide from a Novice
Bounded Arithmetic is a field of mathematical logic which, very roughly, studies subtheories of Peano Arithmetic that "correspond" with reasoning associated with computational complexity classes or propositional proof systems. At the Simons Institute program for Meta Complexity this winter, many attendants (including myself) wished to learn bounded arithmetic due to its increasing appearances and connections with other areas of complexity. Marco Carmosino, Oliver Korten, and Jan Pich organized a bounded arithmetic reading group to go through many elementary and recent works in bounded arithmetic, with a preference towards those results relating to meta complexity. However, with the creation of the reading group, a running joke was spawned: " I won't define this bounded arithmetic theory " Every week we would talk about some results in bounded arithmetic, but the speaker would usually not formally define any of the objects discussed! This is because the logical...