文章基本信息

标题：P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
本地全文：下载
作者：Titus Dose
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-14
DOI：10.4230/LIPIcs.MFCS.2019.47
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Pudlák [P. Pudlák, 2017] lists several major conjectures from the field of proof complexity and asks for oracles that separate corresponding relativized conjectures. Among these conjectures are: - DisjNP: The class of all disjoint NP-pairs has no many-one complete elements. - SAT: NP contains no many-one complete sets that have P-optimal proof systems. - UP: UP has no many-one complete problems. - NP cap coNP: NP cap coNP has no many-one complete problems. As one answer to this question, we construct an oracle relative to which DisjNP, neg SAT, UP, and NP cap coNP hold, i.e., there is no relativizable proof for the implication DisjNP wedge UP wedge NP cap coNP ==> SAT. In particular, regarding the conjectures by Pudlák this extends a result by Khaniki [Khaniki, 2019]. Since Khaniki [Khaniki, 2019] constructs an oracle showing that the implication SAT ==> DisjNP has no relativizable proof, we obtain that the conjectures DisjNP and SAT are independent in relativized worlds, i.e., none of the implications DisjNP ==> SAT and SAT ==> DisjNP can be proven relativizably.
关键词：NP-complete; proof systems; disjoint NP-pair; oracle; UP