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

Titus Dose & Christian Glaßer
The article investigates the relation between three well-known hypotheses. - H_{union}: the union of disjoint ≤^p_m-complete sets for NP is ≤^p_m-complete - H_{opps}: there exist optimal propositional proof systems - H_{cpair}: there exist ≤^{pp}_m-complete disjoint NP-pairs The following results are obtained: - The hypotheses are pairwise independent under relativizable proofs, except for the known implication H_{opps} ⇒ H_{cpair}. - An answer to Pudlák’s question for an oracle relative to which ¬H_{cpair}, ¬H_{opps}, and UP has...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.