文章基本信息

标题：Lower Bounds for Conjunctive and Disjunctive Turing Kernels
本地全文：下载
作者：Burjons, Elisabet ; Rossmanith, Peter
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：214
DOI：10.4230/LIPIcs.IPEC.2021.12
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Parameterized Complexity;Turing kernels