Propositional consistency proofs

DOI10.1016/0168-0072(91)90036-LzbMath0749.03040MaRDI QIDQ1177033

Samuel R. Buss

Publication date: 25 June 1992

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

polynomial bounds; Frege system; mutual consistency proof; propositional calculi

Mathematics Subject Classification ID

03B05: Classical propositional logic

03F20: Complexity of proofs

03F25: Relative consistency and interpretations

Related Items

The Complexity of Propositional Proofs, Frege proof system and TNC°, Towards NP-P via proof complexity and search, Tractability of cut-free Gentzen type propositional calculus with permutation inference, The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem, Quantum deduction rules, Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II, Short proofs of the Kneser-Lovász coloring principle, A bounded arithmetic AID for Frege systems, Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\), QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS, Propositional Proofs in Frege and Extended Frege Systems (Abstract), Frege proof system and TNC°

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems