ECCC-Report TR19-050https://eccc.weizmann.ac.il/report/2019/050Comments and Revisions published for TR19-050en-usTue, 02 Apr 2019 23:32:20 +0300
Paper TR19-050
| NP-Completeness, Proof Systems, and Disjoint NP-Pairs |
Titus Dose,
Christian Glaßer
https://eccc.weizmann.ac.il/report/2019/050The 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.Tue, 02 Apr 2019 23:32:20 +0300https://eccc.weizmann.ac.il/report/2019/050