Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISJOINT NP-PAIR:
Reports tagged with disjoint NP-pair:
TR19-050 | 20th March 2019
Titus Dose, Christian Gla├čer

NP-Completeness, Proof Systems, and Disjoint NP-Pairs

The article investigates the relation between three well-known hypotheses.
1) Hunion: the union of disjoint complete sets for NP is complete for NP
2) Hopps: there exist optimal propositional proof systems
3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:
a) The hypotheses are pairwise independent ... more >>>




ISSN 1433-8092 | Imprint