Expressing versus proving: relating forms of complexity in logic

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Review text

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.

Recommendations

Cited in

(9)

This page was built for publication: Expressing versus proving: relating forms of complexity in logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2882560)