Propositional proof systems, the consistency of first order theories and the complexity of computations

&
Journal of Symbolic Logic 54 (3):1063-1079 (1989)
  Copy   BIBTEX

Abstract

We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in S whose length is ≤ n. We show the relation of this problem to some problems about propositional proof systems

Categories

Keywords

Reprint years

DOI

10.2307/2274765

Other Versions

No versions found

Links

PhilArchive

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Minimum propositional proof length is NP-Hard to linearly approximate.Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi - 2001 - Journal of Symbolic Logic 66 (1):171-191.
On the complexity of Gödel's proof predicate.Yijia Chen & Jörg Flum - 2010 - Journal of Symbolic Logic 75 (1):239-254.
Jan Krajíček and Pavel Pudlák. The number of proof lines and the size of proofs in first order logic. Archive for mathematical logic, vol. 27 , pp. 69–84. [REVIEW]William M. Farmer - 1989 - Journal of Symbolic Logic 54 (3):1107-1108.
New Relations and Separations of Conjectures About Incompleteness in the Finite Domain.Erfan Khaniki - 2022 - Journal of Symbolic Logic 87 (3):912-937.
Propositional Proof Systems and Fast Consistency Provers.Joost J. Joosten - 2007 - Notre Dame Journal of Formal Logic 48 (3):381-398.
On me number of steps in proofs.Jan Krajíèek - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
On the number of steps in proofs.Jan Kraj\mIček - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
Some remarks on lengths of propositional proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.
Combinatorics of first order structures and propositional proof systems.Jan Krajíček - 2004 - Archive for Mathematical Logic 43 (4):427-441.
On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.

Analytics

Added to PP
2009-01-28

Downloads
203 (#198,840)

6 months
62 (#147,885)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.

View all 18 citations / Add more citations

References found in this work

On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.

Add more references