- 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
Simplified Lower Bounds for Propositional Proofs
Notre Dame Journal of Formal Logic 37 (4):523-544 (1996)
Abstract
This article presents a simplified proof of the result that bounded depth propositional proofs of the pigeonhole principle are exponentially large. The proof uses the new techniques for proving switching lemmas developed by Razborov and Beame. A similar result is also proved for some examples based on graphsAuthor'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
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Lower Bounds for cutting planes proofs with small coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Lower Bounds for resolution and cutting plane proofs and monotone computations.Pavel Pudlák - 1997 - Journal of Symbolic Logic 62 (3):981-998.
Lower Bounds to the size of constant-depth propositional proofs.Jan Krajíček - 1994 - Journal of Symbolic Logic 59 (1):73-86.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
2-Exp Time lower bounds for propositional dynamic logics with intersection.Martin Lange & Carsten Lutz - 2005 - Journal of Symbolic Logic 70 (4):1072-1086.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
Quantified propositional logic and the number of lines of tree-like proofs.Alessandra Carbone - 2000 - Studia Logica 64 (3):315-321.
Effective Bounds from ineffective proofs in analysis: An application of functional interpretation and majorization.Ulrich Kohlenbach - 1992 - Journal of Symbolic Logic 57 (4):1239-1273.
Analytics
Added to PP
2010-08-24
Downloads
20 (#747,345)
6 months
4 (#790,687)
2010-08-24
Downloads
20 (#747,345)
6 months
4 (#790,687)
Historical graph of downloads
Author's Profile
Citations of this work
Partially definable forcing and bounded arithmetic.Albert Atserias & Moritz Müller - 2015 - Archive for Mathematical Logic 54 (1):1-33.
Bounded-depth Frege complexity of Tseitin formulas for all graphs.Nicola Galesi, Dmitry Itsykson, Artur Riazanov & Anastasia Sofronova - 2023 - Annals of Pure and Applied Logic 174 (1):103166.
Matrix identities and the pigeonhole principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
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-7c76586df8-pp8v9 uwo