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

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
Keywords Mathematics   Algebra   Mathematics, general   Mathematical Logic and Foundations
Categories (categorize this paper)
DOI 10.1007/s00153-008-0068-4
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 57,109
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Complexity of Propositional Proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
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 index
2013-11-23

Total views
31 ( #333,524 of 2,411,471 )

Recent downloads (6 months)
4 ( #188,489 of 2,411,471 )

How can I increase my downloads?

Downloads

My notes