首页    期刊浏览 2024年07月22日 星期一
登录注册

文章基本信息

  • 标题:NP-Completeness, Proof Systems, and Disjoint NP-Pairs
  • 本地全文:下载
  • 作者:Titus Dose ; Christian Glaßer
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-52
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The article investigates the relation between three well-known hypotheses. 1) Hunion: the union of disjoint complete sets for NP is complete for NP 2) Hopps: there exist optimal propositional proof systems 3) Hcpair: there exist complete disjoint NP-pairs

    The following results are obtained: a) The hypotheses are pairwise independent under relativizable proofs, except for the known implication Hopps \Rightarrow Hcpair. b)Answers to questions by Pudlák in terms of an oracle relative to which \neg Hcpair, \neg Hopps, UP has many-one-complete sets, but NP \cap coNP has no many-one-complete sets. c) The converse of Koebler, Messner, and Toran's implication NEE \cap TALLY \subseteq coNEE \Rightarrow Hopps fails relative to an oracle, where NEE := NTIME(2^{O(2^n)}). d) New characterizations of Hunion and two variants in terms of coNP-completeness and P-producibility of the set of hard formulas of propositional proof systems.

  • 关键词:disjoint NP-pair ; NP-complete ; oracle ; Propositional Proof System
国家哲学社会科学文献中心版权所有