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. Correspond here can mean multiple things, but the two most common interpretations would be the prized Witnessing Theorems or Paris-Wilkies Propositional Translations. 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 we...