Optimal sparsification for some binary CSPs using low-degree polynomials

DOI10.4230/LIPICS.MFCS.2016.71MaRDI QIDQ4608634zbMATH OpenOpenAlexFDO

Authors Bart M. P. Jansen, Astrid Pieterse

Publication date 21 March 2018

Full work available at URL https://arxiv.org/abs/1606.03233

zbMATH Keywords

satisfiabilitysparsificationkernelizationconstraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: This paper analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP is not contained in coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of CNF-SAT with d literals per clause, to equivalent instances with $O(n^{d-e})$ bits for any e > 0. For the Not-All-Equal SAT problem, a compression to size $O(n^{d-1})$ exists. We put these results in a common framework by analyzing the compressibility of binary CSPs. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with $O(n^{2-e})$ bits for any e > 0, unless NP is a subset of coNP/poly.

Recommendations

• Optimal sparsification for some binary CSPs using low-degree polynomials
• Best-case and worst-case sparsifiability of Boolean CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• Sparsification of SAT and CSP Problems via Tractable Extensions
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT

Cited in

(12)

• Optimal sparsification for some binary CSPs using low-degree polynomials
• Optimal data reduction for graph coloring using low-degree polynomials
• Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• scientific article; zbMATH DE number 7536562 (Why is no real title available?)
• Optimal data reduction for graph coloring using low-degree polynomials
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Sparsification of two-variable valued constraint satisfaction problems
• Best-case and worst-case sparsifiability of Boolean CSPs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• On the limits of sparsification
• Best-case and worst-case sparsifiability of Boolean CSPs

This page was built for publication: Optimal sparsification for some binary CSPs using low-degree polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608634)