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.

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,722

External links

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.

Analytics

Added to PP
2009-01-28

Downloads
27 (#427,999)

6 months
1 (#388,319)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Jeremy Avigad
Carnegie Mellon University

References found in this work

Propositional Consistency Proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.

Add more references

Similar books and articles

Theorem Counting.M. G. Beavers - 1994 - Topoi 13 (1):61-65.
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.
Lower Bounds for Modal Logics.Pavel Hrubeš - 2007 - Journal of Symbolic Logic 72 (3):941 - 958.
Complementary Logics for Classical Propositional Languages.Achille C. Varzi - 1992 - Kriterion - Journal of Philosophy 4 (1):20-24.
Tautologies From Pseudo-Random Generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.