The Deduction Theorem for Strong Propositional Proof Systems

DOI10.1007/978-3-540-77050-3_20MaRDI QIDQ5458838zbMATH OpenOpenAlexWikidataFDO

Authors 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 of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The deduction theorem for strong propositional proof systems
• Disjoint NP-pairs and propositional proof systems
• Theory and Applications of Models of Computation
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• Mathematical Foundations of Computer Science 2005

Cites work

• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Complexity Measures for Public-Key Cryptosystems
• Disjoint NP-Pairs
• scientific article; zbMATH DE number 440475 (Why is no real title available?)
• scientific article; zbMATH DE number 806744 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• On reducibility and symmetry of disjoint NP pairs.
• Optimal proof systems imply complete sets for promise classes
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Reductions between disjoint NP-pairs
• The complexity of theorem-proving procedures
• The deduction rule and linear and near-linear proof simulations
• The relative efficiency of propositional proof systems
• Tuples of Disjoint NP-Sets

Cited in

(6)

• Strong extension-free proof systems
• Logical Closure Properties of Propositional Proof Systems
• On the correspondence between arithmetic theories and propositional proof systems – a survey
• scientific article; zbMATH DE number 7652671 (Why is no real title available?)
• Nondeterministic functions and the existence of optimal proof systems
• The deduction theorem for strong propositional proof systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458838)