The deduction theorem for strong propositional proof systems

DOI10.1007/S00224-008-9146-6MaRDI QIDQ987382zbMATH OpenOpenAlexWikidataFDO

Authors 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 theoremdisjoint {\textsf{NP}}-pairsFrege systemsoptimal propositional proof systems

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
• Mathematical Foundations of Computer Science 2005
• Canonical disjoint NP-pairs of propositional proof systems

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?)
• Logical Closure Properties of Propositional Proof Systems
• 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 Deduction Theorem for Strong Propositional Proof Systems
• The relative efficiency of propositional proof systems
• Tuples of disjoint \(\mathsf{NP}\)-sets

Cited in

(4)

• Strong extension-free proof systems
• scientific article; zbMATH DE number 5866432 (Why is no real title available?)
• The Deduction Theorem for Strong Propositional Proof Systems
• An oracle with no up-complete sets, but NP = PSPACE

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 Q987382)