Expressing versus proving: relating forms of complexity in logic (Q2882560)

The paper is devoted to the complexity. Several notions of complexity in logic are considered and the connections among them as well as their relationship with computational complexity are studied. It is shown how the complexity of logics in the setting of finite model theory is used to obtain results in bounded arithmetic, stating which functions are provably total in certain weak systems of arithmetic. The topic of formalizing complexity theory using logic and the meta-question of complexity of logical reasoning about complexity-theoretic statements are considered as well. The paper is intended to be a high-level overview, suitable for readers who are not familar with complexity theory and complexity in logic.