Expressing versus proving: relating forms of complexity in logic
type: Item
instance of: scholarly article
zbMATH Open document ID: 1256.03045
author: Antonina Kolokolova
publication date: 2012-05-07T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 6031075
zbMATH Keywords: survey paper
zbMATH Keywords: complexity in logic
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: descriptive complexity
zbMATH Keywords: proof complexity
MaRDI profile type: Publication
full work available at URL: exq008
OpenAlex ID: W2029183607
DOI: 10.1093/LOGCOM/EXQ008
Recommended article: Logic between Expressivity and Complexity
Recommended article: Q3698794
Recommended article: Q3000099
Recommended article: Q4010371
Recommended article: Q5593816
Recommended article: The Complexity of Propositional Proofs
Recommended article: Q4390867
Recommended article: Q4790400
Recommended article: Q4723713
title: Expressing versus proving: relating forms of complexity in logic
published in: Journal of Logic and Computation
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.
reviewed by: Roman Murawski
description: scientific article; zbMATH DE number 6031075