The deduction theorem for strong propositional proof systems
From MaRDI portal
Publication:987382
DOI10.1007/s00224-008-9146-6zbMath1202.03064WikidataQ59903234 ScholiaQ59903234MaRDI QIDQ987382
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
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