License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.47
URN: urn:nbn:de:0030-drops-109918
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10991/
Go to the corresponding LIPIcs Volume Portal

Dose, Titus

P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle

pdf-format:
LIPIcs-MFCS-2019-47.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{dose:LIPIcs:2019:10991,
  author =	{Titus Dose},
  title =	{{P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10991},
  URN =		{urn:nbn:de:0030-drops-109918},
  doi =		{10.4230/LIPIcs.MFCS.2019.47},
  annote =	{Keywords: NP-complete, proof systems, disjoint NP-pair, oracle, UP}
}

Keywords: NP-complete, proof systems, disjoint NP-pair, oracle, UP
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI