Disjoint NP-pairs and propositional proof systems

zbMATH Open1119.03059MaRDI QIDQ3436752FDOQ3436752

Authors: Olaf Beyersdorff 

Publication date: 11 May 2007

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

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)

Cited In (14)

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

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)