Disjoint NP-pairs and propositional proof systems

MaRDI QIDQ3436752zbMATHFDO

Authors Olaf Beyersdorff

Publication date 11 May 2007

zbMATH Keywords

bounded arithmeticpropositional proof complexitydisjoint NP-pairscomplexity class

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Recommendations

• Theory and Applications of Models of Computation
• Tuples of Disjoint NP-Sets
• Tuples of disjoint \(\mathsf{NP}\)-sets
• Mathematical Foundations of Computer Science 2005
• Classes of representable disjoint \textsf{NP}-pairs

Cited in

(14)

• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Canonical disjoint NP-pairs of propositional proof systems
• The deduction theorem for strong propositional proof systems
• Expansion-based QBF solving versus Q-resolution
• Disjoint NP-Pairs
• scientific article; zbMATH DE number 1834681 (Why is no real title available?)
• Classes of representable disjoint \textsf{NP}-pairs
• Mathematical Foundations of Computer Science 2005
• The Deduction Theorem for Strong Propositional Proof Systems
• On reducibility and symmetry of disjoint NP pairs.
• Tuples of Disjoint NP-Sets
• Inseparability and strong hypotheses for disjoint NP pairs
• The Informational Content of Canonical Disjoint NP-Pairs

This page was built for publication: Disjoint NP-pairs and propositional proof systems

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