License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.12
URN: urn:nbn:de:0030-drops-153953
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15395/
Go to the corresponding LIPIcs Volume Portal

Burjons, Elisabet ; Rossmanith, Peter

Lower Bounds for Conjunctive and Disjunctive Turing Kernels

pdf-format:
LIPIcs-IPEC-2021-12.pdf (0.8 MB)

Abstract

The non-existence of polynomial kernels for OR- and AND-compositional problems is now a well-established result. Some of these problems have adaptive or non-adaptive polynomial Turing kernels. Up to now, most known polynomial Turing kernels are non-adaptive and most of them are of the conjunctive or disjunctive kind. For some problems it has been conjectured that the existence of polynomial Turing kernels is unlikely. For instance, either all or none of the WK[1]-complete problems have polynomial Turing kernels. While it has been conjectured that they do not, a proof tying their non-existence to some complexity theoretic assumption is still missing and seems to be beyond the reach of today’s standard techniques.
In this paper, we prove that OR-compositional problems and all WK[1]-hard problems do not have conjunctive polynomial kernels, a special type of non-adaptive Turing kernels, under the assumption that coNP ⊈ NP/poly. Similarly, it is unlikely that AND-compositional problems have disjunctive polynomial kernels. Moreover, we present a way to prove that the parameterized versions of some ⊕ P-hard problems, for instance, Odd Path on planar graphs, do not have conjunctive or disjunctive polynomial kernels, unless coNP ⊆ NP/poly. Finally, we identify a problem that is unlikely to have either a conjunctive or disjunctive polynomial kernel, unless coNP ⊆ NP/poly, due to a reduction from an NP-hard problem instead: Weighted Odd Path on planar graphs.

BibTeX - Entry

@InProceedings{burjons_et_al:LIPIcs.IPEC.2021.12,
  author =	{Burjons, Elisabet and Rossmanith, Peter},
  title =	{{Lower Bounds for Conjunctive and Disjunctive Turing Kernels}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15395},
  URN =		{urn:nbn:de:0030-drops-153953},
  doi =		{10.4230/LIPIcs.IPEC.2021.12},
  annote =	{Keywords: Parameterized Complexity, Turing kernels}
}

Keywords: Parameterized Complexity, Turing kernels
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021

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