Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
复制标题
DOI：
10.1145/2629620
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Holger Dell;D. Melkebeek
中科院分区：
文献类型：
--
作者：
Holger Dell;D. Melkebeek
考虑下面的两个参与者通信过程来决定语言L：第一个参与者拥有整个输入x，但多项式有界;第二个参与者在计算上是无界的，但不知道x的任何部分;他们的目标是以小成本合作决定x是否属于L，其中成本度量是从第一个参与者到第二个参与者的通信比特数。对于任何整数d ≥ 3和正的真实的ε，我们证明，如果n变量d-CNF公式的可满足性具有成本O（nd-ε）的协议，则coNP处于NP/poly中，这意味着多项式时间层次崩溃到其第三层。这个结果甚至在第一个参与者是conondeterministic时也成立，并且是紧的，因为存在一个ε = 0的平凡协议。在假设coNP不是NP/poly的情况下，我们的结果意味着在几个领域，即稀疏化，参数化复杂性的核化，有损压缩和概率可检查的证明中，感兴趣的参数的严格下限。通过约化，类似的结果也适用于其他NP完全问题。对于n-顶点d-一致超图上的顶点覆盖问题，这个命题对任意整数d ≥ 2都成立。d = 2的情况意味着，基于子图继承的图属性的NP难顶点删除问题的核可以由O（k2 − ε）条边组成，除非coNP是NP/poly，其中k表示删除集的大小。由O（k2）条边组成的核在该类中的几个问题中是已知的，包括顶点覆盖，反馈顶点集和有界度删除。
Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to decide cooperatively whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d ≥ 3 and positive real ε, we show that, if satisfiability for n-variable d-CNF formulas has a protocol of cost O(nd − ε), then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for ε = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on n-vertex d-uniform hypergraphs, this statement holds for any integer d ≥ 2. The case d = 2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O(k2 − ε) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O(k2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.