- 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
Plausibly hard combinatorial tautologies
Abstract
We present a simple propositional proof system which consists of a single axiom schema and a single rule, and use this system to construct a sequence of combinatorial tautologies that, when added to any Frege system, p-simulates extended-Frege systems.Author'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
- Only published works are available at libraries.
My notes
Similar books and articles
Reasoning processes in propositional logic.Claes Strannegård, Simon Ulfsbäcker, David Hedqvist & Tommy Gärling - 2010 - Journal of Logic, Language and Information 19 (3):283-314.
Logics of rejection: two systems of natural deduction.Allard Tamminga - 1994 - Logique Et Analyse 146:169-208.
Complementary Logics for Classical Propositional Languages.Achille C. Varzi - 1992 - Kriterion - Journal of Philosophy 4 (1):20-24.
The deduction rule and linear and near-linear proof simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Structured Pigeonhole Principle, Search Problems and Hard Tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619 - 630.
Analytics
Added to PP
2009-01-28
Downloads
31 (#501,295)
6 months
4 (#818,853)
2009-01-28
Downloads
31 (#501,295)
6 months
4 (#818,853)
Historical graph of downloads
Author's Profile
Citations of this work
The provably total NP search problems of weak second order bounded arithmetic.Leszek Aleksander Kołodziejczyk, Phuong Nguyen & Neil Thapen - 2011 - Annals of Pure and Applied Logic 162 (6):419-446.
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.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
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-l2pxr uwo