The deduction theorem for strong propositional proof systems

DOI10.1007/s00224-008-9146-6zbMath1202.03064WikidataQ59903234 ScholiaQ59903234MaRDI QIDQ987382

Olaf Beyersdorff

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/74443/2/deduction_revised.pdf

zbMATH Keywords

deduction theorem; Frege systems; disjoint {\textsf{NP}}-pairs; optimal propositional proof systems

Mathematics Subject Classification ID

03B05: Classical propositional logic

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F20: Complexity of proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Tuples of disjoint \(\mathsf{NP}\)-sets
• 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
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Logical Closure Properties of Propositional Proof Systems
• Complexity Measures for Public-Key Cryptosystems
• The relative efficiency of propositional proof systems
• Disjoint NP-Pairs
• The Deduction Theorem for Strong Propositional Proof Systems
• The complexity of theorem-proving procedures