Holger Dell
ABSTRACT
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 cooperatively decide 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, the above 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(k^2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.
- D. Achlioptas and C. Moore. Random k-SAT: two moments suffice to cross a sharp threshold. SICOMP, 36(3):740--762, 2007. Google Scholar
Digital Library
- D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2k log 2-O(k). Journal of the AMS, 17(4):947--973, 2004.Google Scholar
- N. Alon. Testing subgraphs in large graphs. RSA, 21(3--4):359--370, 2002. Google ScholarDigital Library
- N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451--476, 2000.Google ScholarCross Ref
- N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. SIAM Journal on Discrete Mathematics, 22(2):786--819, 2008. Google ScholarDigital Library
- N. Alon and A. Shapira. Testing subgraphs in directed graphs. JCSS, 69(3):354--382, 2004. Google ScholarDigital Library
- N. Alon and A. Shapira. Linear equations, arithmetic progressions and hypergraph property testing. Theory of Computing, 1(1):177--216, 2005.Google ScholarCross Ref
- N. Alon and A. Shapira. A characterization of easily testable induced subgraphs. Combinatorics, Probability and Computing, 15(6):791--805, 2006. Google ScholarDigital Library
- H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin. On problems without polynomial kernels. JCSS, 75(8):423--434, 2009. Google ScholarDigital Library
- H. L. Bodlaender, S. Thomasse, and A. Yeo. Kernel bounds for disjoint cycles and disjoint paths. In ESA, pages 635--646, 2009.Google ScholarCross Ref
- J. F. Buss and J. Goldsmith. Nondeterminism within P. SICOMP, 22(3):560--572, 1993. Google ScholarDigital Library
- C. Calabro, R. Impagliazzo, and R. Paturi. A duality between clause width and clause density for SAT. In CCC, pages 252--260, 2006. Google ScholarDigital Library
- A. K. Chandra, M. L. Furst, and R. J. Lipton. Multi-party protocols. In STOC, pages 94--99, 1983. Google ScholarDigital Library
- Y. Chen, J. Flum, and M. Muller. Lower bounds for kernelizations. ECCC, 14(137), 2007.Google Scholar
- S. A. Cook. The complexity of theorem-proving procedures. In STOC, pages 151--158, 1971. Google ScholarDigital Library
- D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251--280, 1990. Google ScholarDigital Library
- H. Dell and D. van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. ECCC, 17(38), 2010.Google Scholar
- I. Dinur. The PCP theorem by gap amplification. JACM, 54(3):12, 2007. Google ScholarDigital Library
- M. Dom, D. Lokshtanov, and S. Saurabh. Incompressibility through colors and IDs. In ICALP, pages 378--389, 2009. Google ScholarDigital Library
- P. Erdos and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 35:85--90, 1960.Google ScholarCross Ref
- M. R. Fellows, J. Guo, H. Moser, and R. Niedermeier. A generalization of Nemhauser and Trotter's local optimization theorem. In STACS, pages 409--420, 2009.Google Scholar
- H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible, S. Saurabh, and Y. Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. In STACS, pages 421--432, 2009.Google Scholar
- J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. Google ScholarDigital Library
- L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. In STOC, pages 133--142, 2008. Google ScholarDigital Library
- E. Friedgut and J. Bourgain. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the AMS, 12(4):1017--1054, 1999.Google Scholar
- O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. JACM, 45(4):653--750, 1998. Google ScholarDigital Library
- J. Guo and R. Niedermeier. Invitation to data reduction and problem kernelization. SIGACT News, 38(1):31--45, 2007. Google ScholarDigital Library
- D. Harnik and M. Naor. On the compressibility of NP instances and cryptographic applications. In FOCS, pages 719--728, 2006. Google ScholarDigital Library
- J. Haastad and A. Wigderson. Simple analysis of graph tests for linearity and PCP. RSA, 22(2):139--160, 2003. Google ScholarDigital Library
- R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? JCSS, 63(4):512--530, 2001. Google ScholarDigital Library
- R. M. Karp. Reducibility among combinatorial problems. Complexity of computer computations, 43:85--103, 1972.Google Scholar
- S. Kratsch and M. Wahlstrom. Preprocessing of min ones problems: A dichotomy. Arxiv Preprint, 2009.Google Scholar
- S. Kratsch and M. Wahlstrom. Two edge modification problems without polynomial kernels. In IWPEC, pages 264--275, 2009. Google ScholarDigital Library
- M. S. Krishnamoorthy and N. Deo. Node-deletion NP-complete problems. SICOMP, 8(4):619--625, 1979.Google ScholarCross Ref
- L. A. Levin. Universal search problems. Problemy Peredachi Informatsii, 9(3):265--266, 1973.Google Scholar
- J. M. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete. JCSS, 20(2):219--230, 1980.Google ScholarCross Ref
- I. Z. Ruzsa and E. Szemeredi. Triple systems with no six points carrying three triangles. In Combinatorics, Vol. II, volume 18 of Colloquia Mathematica Societatis Janos Bolyai, pages 939--945. North-Holland, 1978.Google Scholar
- R. Salem and D. C. Spencer. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences, USA, 28(12):561--563, 1942.Google ScholarCross Ref
- S. Thomasse. A quadratic kernel for feedback vertex set. In SODA, pages 115--119, 2009. Google ScholarDigital Library
- C.-K. Yap. Some consequences of non-uniform conditions on uniform classes. TCS, 26(3):287--300, 1983.Google ScholarCross Ref
Index Terms
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Recommendations
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
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 ...
Parameterized complexity of vertex deletion into perfect graph classes
Vertex deletion problems are at the heart of parameterized complexity. For a graph class F, the F-Deletion problem takes as input a graph G and an integer k. The question is whether it is possible to delete at most k vertices from G such that the ...
On Sparsification for Computing Treewidth
We investigate whether an $$n$$n-vertex instance $$(G,k)$$(G,k) of Treewidth, asking whether the graph $$G$$G has treewidth at most $$k$$k, can efficiently be made sparse without changing its answer. By giving a special form of $$\mathop {\mathrm {\...
Comments