文章基本信息

标题：NP-Completeness, Proof Systems, and Disjoint NP-Pairs
本地全文：下载
作者：Titus Dose ; Christian Gla{\ss}er
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：9:1-9:18
DOI：10.4230/LIPIcs.STACS.2020.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 â¤^p_m-complete sets. - The converse of KÃ¶bler, Messner, and TorÃ¡nâs implication NEE â^© TALLY âS coNEE â' H_{opps} fails relative to an oracle, where NEE =^{df} NTIME(2^O(2â¿)). - New characterizations of H_{union} and two variants in terms of coNP-completeness and p-producibility of the set of hard formulas of propositional proof systems.
关键词：NP-complete; propositional proof system; disjoint NP-pair; oracle