The deduction theorem for strong propositional proof systems
type: Item
instance of: scholarly article
title: The deduction theorem for strong propositional proof systems
zbMATH Open document ID: 1202.03064
author: Olaf Beyersdorff
published in: Theory of Computing Systems
publication date: 2010-08-13T00:00:00Z
full work available at URL: deduction revised.pdf
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03B05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5770227
zbMATH Keywords: deduction theorem
zbMATH Keywords: optimal propositional proof systems
zbMATH Keywords: disjoint {\textsf{NP}}-pairs
zbMATH Keywords: Frege systems
MaRDI profile type: Publication
Wikidata QID: Q59903234
OpenAlex ID: W1993478355
cites work: Classes of representable disjoint \textsf{NP}-pairs
cites work: The Deduction Theorem for Strong Propositional Proof Systems
cites work: Logical Closure Properties of Propositional Proof Systems
cites work: Tuples of disjoint \(\mathsf{NP}\)-sets
cites work: Q3140632
cites work: The deduction rule and linear and near-linear proof simulations
cites work: Q4850545
cites work: The complexity of theorem-proving procedures
cites work: The relative efficiency of propositional proof systems
cites work: Reductions between disjoint NP-pairs
cites work: Disjoint NP-Pairs
cites work: Canonical disjoint NP-pairs of propositional proof systems
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Oracles for structural properties: The isomorphism problem and public-key cryptography
cites work: Optimal proof systems imply complete sets for promise classes
cites work: Q4856172
cites work: Propositional proof systems, the consistency of first order theories and the complexity of computations
cites work: On reducibility and symmetry of disjoint NP pairs.
cites work: On an optimal propositional proof system and the structure of easy subsets of TAUT.
DOI: 10.1007/S00224-008-9146-6
description: scientific article; zbMATH DE number 5770227