The deduction theorem for strong propositional proof systems

DOI10.1007/S00224-008-9146-6zbMath1202.03064OpenAlexW1993478355WikidataQ59903234 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 theoremFrege systemsdisjoint {\textsf{NP}}-pairsoptimal propositional proof systems

Mathematics Subject Classification ID

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

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

This page was built for publication: The deduction theorem for strong propositional proof systems