Logical Closure Properties of Propositional Proof Systems

DOI10.1007/978-3-540-79228-4_28zbMath1139.03316OpenAlexW1566692464WikidataQ59903870 ScholiaQ59903870MaRDI QIDQ3502657

Olaf Beyersdorff

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_28

zbMATH Keywords

extended Frege proof system

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20)

Related Items (2)

The deduction theorem for strong propositional proof systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classes of representable disjoint \textsf{NP}-pairs
• Optimal proof systems imply complete sets for promise classes
• On reducibility and symmetry of disjoint NP pairs.
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• On the automatizability of resolution and related propositional proof systems
• The deduction rule and linear and near-linear proof simulations
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Quantified propositional calculi and fragments of bounded arithmetic
• Complexity Measures for Public-Key Cryptosystems
• Rudimentary Predicates and Relative Computation
• The relative efficiency of propositional proof systems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• The Deduction Theorem for Strong Propositional Proof Systems

This page was built for publication: Logical Closure Properties of Propositional Proof Systems