The Deduction Theorem for Strong Propositional Proof Systems

DOI10.1007/978-3-540-77050-3_20zbMath1135.03347OpenAlexW1649430738WikidataQ59904010 ScholiaQ59904010MaRDI QIDQ5458838

Olaf Beyersdorff

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_20

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (4)

Nondeterministic functions and the existence of optimal proof systems ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ 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
• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• 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.
• Reductions between disjoint NP-pairs
• The deduction rule and linear and near-linear proof simulations
• Tuples of Disjoint NP-Sets
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Complexity Measures for Public-Key Cryptosystems
• The relative efficiency of propositional proof systems
• Disjoint NP-Pairs
• The complexity of theorem-proving procedures

This page was built for publication: The Deduction Theorem for Strong Propositional Proof Systems