Proof system representations of degrees of disjoint NP-pairs

DOI10.1016/j.ipl.2011.01.001zbMath1260.68149OpenAlexW1969650910MaRDI QIDQ1944897

Liyu Zhang

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.01.001

zbMATH Keywords

computational complexitypropositional proof systemscanonical NP-pairsdegrees of disjoint NP-pairs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• On reducibility and symmetry of disjoint NP pairs.
• Inseparability and Strong Hypotheses for Disjoint NP Pairs.
• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• Complexity Measures for Public-Key Cryptosystems
• The relative efficiency of propositional proof systems
• Disjoint NP-Pairs
• Theory and Applications of Models of Computation
• Computability and complexity theory

This page was built for publication: Proof system representations of degrees of disjoint NP-pairs