- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
On meta complexity of propositional formulas and propositional proofs
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 complexityAuthor's Profile
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
On transformations of constant depth propositional proofs.Arnold Beckmann & Sam Buss - 2019 - Annals of Pure and Applied Logic 170 (10):1176-1187.
Upper bounds on complexity of Frege proofs with limited use of certain schemata.Pavel Naumov - 2006 - Archive for Mathematical Logic 45 (4):431-446.
Partially definable forcing and bounded arithmetic.Albert Atserias & Moritz Müller - 2015 - Archive for Mathematical Logic 54 (1):1-33.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Substitution and Propositional Proof Complexity.Sam Buss - 2021 - In Ivo Düntsch & Edwin Mares (eds.), Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs. Springer Verlag. pp. 477-496.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
Proof complexity of propositional default logic.Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas & Heribert Vollmer - 2011 - Archive for Mathematical Logic 50 (7-8):727-742.
Counting proofs in propositional logic.René David & Marek Zaionc - 2009 - Archive for Mathematical Logic 48 (2):185-199.
Combinatorics of first order structures and propositional proof systems.Jan Krajíček - 2004 - Archive for Mathematical Logic 43 (4):427-441.
Analytics
Added to PP
2013-11-23
Downloads
45 (#343,445)
6 months
12 (#306,613)
2013-11-23
Downloads
45 (#343,445)
6 months
12 (#306,613)
Historical graph of downloads
Author's Profile
References found in this work
The relative efficiency of propositional proof systems.Stephen A. Cook & Robert A. Reckhow - 1979 - Journal of Symbolic Logic 44 (1):36-50.
Structured Pigeonhole Principle, Search Problems and Hard Tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619 - 630.
Structured pigeonhole principle, search problems and hard tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619-630.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-6686886f5-5pqs9 uwo