Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-050 | 20th March 2019 19:01

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


Authors: Titus Dose, Christian Glaßer
Publication: 2nd April 2019 23:32
Downloads: 86


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 under relativizable proofs, except for the known implication Hopps \Rightarrow Hcpair.
b)Answers to questions by Pudlák in terms of an oracle relative to which \neg Hcpair, \neg Hopps, UP has many-one-complete sets, but NP \cap coNP has no many-one-complete sets.
c) The converse of Koebler, Messner, and Toran's implication NEE \cap TALLY \subseteq coNEE \Rightarrow Hopps fails relative to an oracle, where NEE := NTIME(2^{O(2^n)}).
d) New characterizations of Hunion and two variants in terms of coNP-completeness and P-producibility of the set of hard formulas of propositional proof systems.

ISSN 1433-8092 | Imprint