Proof system representations of degrees of disjoint NP-pairs
From MaRDI portal
Publication:1944897
DOI10.1016/j.ipl.2011.01.001zbMath1260.68149MaRDI QIDQ1944897
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
computational complexity; propositional proof systems; canonical NP-pairs; degrees of disjoint NP-pairs
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
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