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 boundsFrege systemmutual consistency proofpropositional calculi

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20) Relative consistency and interpretations (03F25)

Related Items (13)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Propositional consistency proofs