2026-08-02T03:08:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11870 2024-03-06T10:48:53Z ddc:004 open_access

NP-Completeness, Proof Systems, and Disjoint NP-Pairs Dose, Titus Glaßer, Christian NP-complete propositional proof system disjoint NP-pair oracle 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 ⊆ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Titus Dose and Christian Glaßer 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.9 urn:nbn:de:0030-drops-118707 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode