On meta complexity of propositional formulas and propositional proofs

Archive for Mathematical Logic 47 (1):35-52 (2008)
  Copy   BIBTEX

Abstract

A new approach to defining complexity of propositional formulas and proofs is suggested. Instead of measuring the size of these syntactical structures in the propositional language, the article suggests to define the complexity by the size of external descriptions of such constructions. The main result is a lower bound on proof complexity with respect to this new definition of complexity

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
A note on propositional proof complexity of some Ramsey-type statements.Jan Krajíček - 2011 - Archive for Mathematical Logic 50 (1-2):245-255.
Examining fragments of the quantified propositional calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.

Analytics

Added to PP
2013-11-23

Downloads
33 (#419,244)

6 months
3 (#447,120)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Pavel Naumov
University of Southampton

Citations of this work

No citations found.

Add more citations

References found in this work

Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.
Implicit proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387-397.

Add more references