Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
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 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 ( k 2 − ε ) 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385 · cited 2×
“Of particular interest is d-SAT, the satisfiability problem for d-CNF formulas, which is NP-complete for any integer d ≥ 3 [Cook 1971; Karp 1972; Levin 1973].”
Fellows, M. R. (2002) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)00301-9 · Cited by 2,836
Downey, R. G., & Fellows, M. R. (1999) · Monographs in Computer Science · doi:10.1007/978-1-4612-0515-9 · Cited by 2,532
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,359
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
Parameterized Complexity Theory
(2006) · Texts in Theoretical Computer Science. An EATCS Series · doi:10.1007/3-540-29953-x · Cited by 1,869 · cited 1×
“For their soundness analysis of graph tests for linearity, Håstad and Wigderson [2003] use the interpretation that for each of the p points in the first column, the triangles involving that point span an induced matching of p1−o(1) edges between the other columns.”
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
Which Problems Have Strongly Exponential Complexity?
Impagliazzo, R., Paturi, R., & Zane, F. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1774 · Cited by 1,331
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,020
The Complexity of Boolean Functions
Wegener, I. (1987) · Cited by 925
Multiplying matrices faster than coppersmith-winograd
Williams, V. V. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2214056 · Cited by 850 · cited 3×
“…the asymptotically fastest algorithms for matrix multiplication [Coppersmith and Winograd 1990; Davie and Stothers 2013; Stothers 2010; Vassilevska Williams 2012], the soundness analysis of graph tests for linearity [H °astad and Wigderson 2003], and lower bounds for property testing [Alon…”
InfluentialSharp thresholds of graph properties, and the $k$-sat problem
Friedgut, E., & Jean Bourgain, A. B. (1999) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-99-00305-7 · Cited by 678 · cited 1×
“We know that the probability of satis.ability jumps from almost zero to almost one when the ratio m/n crosses a very narrow region around 2d ln 2, and the existence of a single threshold point is conjectured [Achlioptas and Moore 2007; Achlioptas and Peres 2004; Friedgut and Bourgain 1999].”
Intersection Theorems for Systems of Sets
Erdös, P., & Rado, R. (1960) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-35.1.85 · Cited by 626
On problems without polynomial kernels
Bodlaender, H. L., Downey, R. G., Fellows, M. R., & Hermelin, D. (2009) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2009.04.001 · Cited by 592 · cited 1×
“Several authors subsequently applied the framework in that setting [Binkele-Raible et al. 2012; Bodlaender et al. 2009b; Chen et al. 2007; Dom et al. 2009; Kratsch and Wahlstr ¨ om 2010, 2013].”
The node-deletion problem for hereditary properties is NP-complete
Lewis, J. M., & Yannakakis, M. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90060-4 · Cited by 513 · cited 4×
“For all other graph properties that are inherited by subgraphs, Lewis and Yannakakis [1980] showed that the problem is NP-hard.”
InfluentialThe PCP theorem by gap amplification
Dinur, I. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132553 · Cited by 501
Computational complexity: a conceptual perspective
(2008) · Choice Reviews Online · doi:10.5860/choice.46-0942 · Cited by 421
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
Behrend, F. A. (1946) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.32.12.331 · Cited by 408
Buss, J. F., & Goldsmith, J. (1993) · SIAM Journal on Computing · doi:10.1137/0222038 · Cited by 308 · cited 3×
“For standard graphs, S. Buss [Buss and Goldsmith 1993] came up with a kernelization before the term was coined.”
InfluentialInfeasibility of instance compression and succinct PCPs for NP
Fortnow, L., & Santhanam, R. (2011) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2010.06.007 · Cited by 288
A 4 k 2 kernel for feedback vertex set
Thomassé, S. (2010) · ACM Transactions on Algorithms · doi:10.1145/1721837.1721848 · Cited by 194
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
(2005) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898715859 · Cited by 181
On the complexity of matrix multiplication
Stothers, A. J. (2010) · ERA · Cited by 167
Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
Achlioptas, D., & Moore, C. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539703434231 · Cited by 163 · cited 3×
“We know that the probability of satisfiability jumps from almost zero to almost one when the ratio m/n crosses a very narrow region around 2d ln 2, and the existence of a single threshold point is conjectured [Achlioptas and Moore 2007; Achlioptas and Peres 2004; Friedgut and Bourgain 1999].”
Improved bound for complexity of matrix multiplication
Davie, A. M., & Stothers, A. J. (2013) · Proceedings of the Royal Society of Edinburgh: Section A Mathematics · doi:10.1017/s0308210511001648 · Cited by 152 · cited 2×
“1983], the asymptotically fastest algorithms for matrix multiplication [Coppersmith and Winograd 1990; Davie and Stothers 2013; Stothers 2010; Vassilevska Williams 2012], the soundness analysis of graph tests for linearity [Håstad and Wigderson 2003], and lower bounds for property testing [Alon 2002; Alon et al.”
On self-reducibility and weak P-selectivity
Ko, K. (1983) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(83)90013-2 · Cited by 149
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
Salem, R., & Spencer, D. C. (1942) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.28.12.561 · Cited by 132
Complexity measures of sign matrices
Linial, N., Mendelson, S., Schechtman, G., & Shraibman, A. (2007) · COMBINATORICA · doi:10.1007/s00493-007-2160-5 · Cited by 129
A generalization of Nemhauser and Trotterʼs local optimization theorem
Fellows, M. R., Guo, J., Moser, H., & Niedermeier, R. (2010) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2010.12.001 · Cited by 100
New Limits to Classical and Quantum Instance Compression
Drucker, A. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.71 · Cited by 95
Simple analysis of graph tests for linearity and PCP
Håstad, J., & Wigderson, A. (2003) · Random Structures and Algorithms · doi:10.1002/rsa.10068 · Cited by 85
On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
Harnik, D., & Naor, M. (2010) · SIAM Journal on Computing · doi:10.1137/060668092 · Cited by 85
Node-Deletion NP-Complete Problems
Krishnamoorthy, M. S., & Deo, N. (1979) · SIAM Journal on Computing · doi:10.1137/0208049 · Cited by 81 · cited 2×
“Inthe known reduction from VERTEX COVER to this problem [Krishnamoorthy and Deo 1979], d new edges are attached to every vertex of G (see Figure 2(b)).”
A Note on Elkin’s Improvement of Behrend’s Construction
Green, B., & Wolf, J. (2010) · Springer eBooks · doi:10.1007/978-0-387-68361-4_9 · Cited by 61
Freiman's Theorem in Finite Fields via Extremal Set Theory
Green, B., & Tao, T. (2009) · Combinatorics Probability Computing · doi:10.1017/s0963548309009821 · Cited by 39
A note on Freiman’s theorem in vector spacesPreprint
Sanders, T. (n.d.) · Cited by 27
A Note on Freĭman's Theorem in Vector Spaces
SANDERS, T. (2007) · Combinatorics Probability Computing · doi:10.1017/s0963548307008644 · Cited by 22
Metadata
- Authors
- Dell, H., & Van Melkebeek, D.
- Venue
- Journal of the ACM
- Published
- 2014-07
- Volume
- 61
- Issue
- 4
- Pages
- 1-27
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2034437384
- Cited by
- 159
- References
- 39
- FWCI
- 10.72
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.