文章基本信息
- 标题：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
