Constraint satisfaction problems with global modular constraints: algorithms and hardness via polynomial representations. (English) Zbl 07538272
Summary: We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo \(M\), for various choices of the modulus \(M\). Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2-SAT, HORN-SAT, and LIN-2 (linear equations mod 2). We classify the moduli \(M\) for which these respective problems are polynomial time solvable, and when they are not (assuming the exponential time hypothesis). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HORN-SAT case is connected to the covering complexity of polynomials representing the NAND function mod \(M\). The LIN-2 case is tied to the sparsity of polynomials representing the OR function mod \(M\), which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by Nägele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HORN-SAT has strong similarities to their algorithm, and in particular identical kinds of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite \(M\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R07 | Computational aspects of satisfiability |
| 68W40 | Analysis of algorithms |
| 94B05 | Linear codes (general theory) |
Keywords:
constraint satisfaction problems; computational complexity; algorithms; error-correcting codesReferences:
| [1] | E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer, The complexity of satisfiability problems: Refining schaefer’s theorem, J. Comput. System Sci., 75 (2009), pp. 245-254. · Zbl 1161.68487 |
| [2] | V. Arvind and V. Guruswami, CNF satisfiability in a subspace and related problems, in Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021. · Zbl 07803583 |
| [3] | S. Artmann, R. Weismantel, and R. Zenklusen, A strongly polynomial algorithm for bimodular integer linear programming, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 1206-1219. · Zbl 1369.68350 |
| [4] | D. A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^1\), J. Comput. System Sci., 38 (1989), pp. 150-164. · Zbl 0667.68059 |
| [5] | D. A Mix Barrington, R. Beigel, and S. Rudich, Representing boolean functions as polynomials modulo composite numbers, Comput. Complexity, 4 (1994), pp. 367-382. · Zbl 0829.68057 |
| [6] | A. Bhowmick, Z. Dvir, and S. Lovett, New bounds for matching vector families, SIAM J. Comput., 43 (2014), pp. 1654-1683. · Zbl 1314.05204 |
| [7] | J. Brakensiek and V. Guruswami, New hardness results for graph and hypergraph colorings, in Proceedings of the 31st Conference on Computational Complexity, LIPIcs Leibniz Int. Proc. Inform. 50, Schloss Dagstuhl - Leibniz-Zentrum füer Informatik, 2016. · Zbl 1380.68190 |
| [8] | A. Bulatov, P. Jeavons, and A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34 (2005), pp. 720-742. · Zbl 1071.08002 |
| [9] | V. G. Bodnarchuk, L. Ao Kaluzhnin, V. N. Kotov, and B. A. Romov, Galois theory for post algebras I, Cybernetics, 5 (1969), pp. 243-252. |
| [10] | M. Bodirsky, J. Kára, and B. Martin, The complexity of surjective homomorphism problems-a survey, Discrete Appl. Math., 160 (2012), pp. 1680-1690. · Zbl 1246.05104 |
| [11] | L. Barto, A. A. Krokhin, and R. Willard, Polymorphisms, and how to use them, in The Constraint Satisfaction Problem: Complexity and Approximability, A. A. Krokhin and S. Zivny, eds., Dagstuhl Follow-Ups 7, Schloss Dagstuhl - Leibniz-Zentrum füer Informatik, 2017, pp. 1-44. · Zbl 1482.68161 |
| [12] | A. A. Bulatov and D. Marx, The complexity of global cardinality constraints, Log. Methods Comput. Sci., 6 (2010). · Zbl 1202.68208 |
| [13] | A. A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a \(3\)-element set, J. ACM, 53 (2006), pp. 66-120. · Zbl 1316.68057 |
| [14] | A. A. Bulatov, A dichotomy theorem for nonuniform csps, in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, Berkeley, CA, C. Umans, ed., 2017, pp. 319-330. |
| [15] | A. Chattopadhyay, N. Goyal, P. Pudlák, and D. Thérien, Lower bounds for circuits with mod_m gates, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA 2006, pp. 709-718, 2006. |
| [16] | H. Chen, A rendezvous of logic, complexity, and algebra, ACM Comput. Surv., 42 (2009), pp. 2:1-2:32. |
| [17] | N. Creignou, P. G. Kolaitis, and B. Zanuttini, Structure identification of boolean relations and plain bases for co-clones, J. Comput. System Sci., 74 (2008), pp. 1103-1115. · Zbl 1152.68020 |
| [18] | S. Cook and P. Nguyen, Logical Foundations of Proof Complexity, Perspect. Log. 11, Cambridge University Press, Cambridge, UK, 2010. · Zbl 1206.03051 |
| [19] | N. Creignou, H. Schnoor, and I. Schnoor, Nonuniform boolean constraint satisfaction problems with cardinality constraint, ACM Trans. Comput. Logic, 11 (2010), pp. 24:1-24:32. · Zbl 1351.68114 |
| [20] | G. Cohen and A. Tal, Two structural results for low degree polynomials and applications, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015, pp. 680-709. · Zbl 1375.11074 |
| [21] | A. Chattopadhyay and A. Wigderson, Linear systems over composite moduli, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, 2009, pp. 43-52. · Zbl 1292.68072 |
| [22] | Z. Dvir and S. Gopi, \(2\)-server pir with subpolynomial communication, J. ACM, 63 (2016), 39. · Zbl 1407.94008 |
| [23] | Z. Dvir, P. Gopalan, and S. Yekhanin, Matching vector codes, SIAM J. Comput., 40 (2011), pp. 1154-1178. · Zbl 1228.68026 |
| [24] | K. Efremenko, \(3\)-query locally decodable codes of subexponential length, SIAM J. Comput., 41 (2012), pp. 1694-1703. · Zbl 1311.94124 |
| [25] | T. Feder and M. Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput., 28 (1998), pp. 57-104. · Zbl 0914.68075 |
| [26] | D. Geiger, Closed systems of functions and predicates, Pacific J. Math., 27 (1968), pp. 95-100. · Zbl 0186.02502 |
| [27] | V. Guruswami and E. Lee, Complexity of approximating CSP with balance / hard constraints, Theory Comput. Sys., 59 (2016), pp. 76-98. · Zbl 1350.68142 |
| [28] | P. Gopalan, A note on Efremenko’s locally decodable codes, Electron. Colloq. Comput. Complex., 16 (2009). |
| [29] | P. Gopalan, Constructing ramsey graphs from boolean function representations, Combinatorica, 34 (2014), pp. 173-206. · Zbl 1349.05230 |
| [30] | V. Grolmusz, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs, Combinatorica, 20 (2000), pp. 71-86. · Zbl 0949.05083 |
| [31] | G. Horv’ath, The complexity of the equivalence and equation solvability problems over meta-Abelian groups, J. Algebra, 433 (2015), pp. 208-230. · Zbl 1364.20016 |
| [32] | P. M. Idziak, P. Kawalek, and J. Krzaczkowski, Complexity of Modular Circuits, CoRR, https://arxiv.org/abs/2106.02947, 2021. · Zbl 07299497 |
| [33] | R. Impagliazzo and R. Paturi, On the complexity of k-SAT, J. Comput. System Sci., 62 (2001), pp. 367-375. · Zbl 0990.68079 |
| [34] | R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, J. Comput. System Sci., 63 (2001), pp. 512-530. · Zbl 1006.68052 |
| [35] | P. Jeavons, On the algebraic structure of combinatorial problems, Theoret. Comput. Sci., 200 (1998), pp. 185-204. · Zbl 0915.68074 |
| [36] | I. Kerenidis and R. De Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, J. Comput. System Sci., 69 (2004), pp. 395-420. · Zbl 1084.68044 |
| [37] | M. R Krom, The decision problem for a class of first-order formulas in which all disjunctions are binary, Math. Logic Quart., 13 (1967), pp. 15-20. · Zbl 0162.31601 |
| [38] | J. Katz and L. Trevisan, On the efficiency of local decoding procedures for error-correcting codes, in Proceedings of the 32nd annual ACM Symposium on Theory of Computing, ACM, 2000, pp. 80-86. · Zbl 1296.94171 |
| [39] | T. Liu and V. Vaikuntanathan, Breaking the circuit-size barrier in secret sharing, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, 2018, pp. 699-708. · Zbl 1428.94108 |
| [40] | D. Moshkovitz and R. Raz, Two-query PCP with subconstant error, J. ACM, 57 (2010), 29. · Zbl 1327.68110 |
| [41] | M. Nägele, B. Sudakov, and R. Zenklusen, Submodular minimization under congruency constraints, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2018, pp. 849-866. · Zbl 1403.68385 |
| [42] | M. Nägele and R. Zenklusen, A new contraction technique with applications to congruency-constrained cuts, in Proceedings of the 20th International Conference on Integer Programming and Combinatorial Optimization, 2019, pp. 327-340. · Zbl 1436.90127 |
| [43] | M. Nägele and R. Zenklusen, A new contraction technique with applications to congruency-constrained cuts, Math. Program., 183 (2020), pp. 455-481. · Zbl 1450.90046 |
| [44] | E. L. Post, The Two-Valued Iterative Systems of Mathematical Logic, Ann. Math. Stud. Princeton University Press, Princeton, NJ, 1941. · Zbl 0063.06326 |
| [45] | J. Paat, M. Schlöter, and R. Weismantel, Most IPs with Bounded Determinants Can Be Solved in Polynomial Time, CoRR, https://arxiv.org/abs/1904.06874, 2019. |
| [46] | T. J. Schaefer, The complexity of satisfiability problems, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM, New York, 1978, pp. 216-226. · Zbl 1282.68143 |
| [47] | G. Tardos and D. A. Mix Barrington, A lower bound on the mod 6 degree of the or function, Comput. Complex., 7 (1998), pp. 99-108. · Zbl 0936.68051 |
| [48] | L. G. Valiant, Short monotone formulae for the majority function, J. Algorithms, 5 (1984), pp. 363-366. · Zbl 0554.94017 |
| [49] | V. V. Vazirani, Approximation Algorithms, Springer, New York, 2013. |
| [50] | A. Weiß, Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis, in 47th International Colloquium on Automata, Languages, and Programming, A. Czumaj, A. Dawar, and E. Merelli, eds., LIPIcs Leibniz Int. Proc. Inform. 168, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020, pp. 102:1-102:19. |
| [51] | S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, J. ACM, 55 (2008). · Zbl 1311.94125 |
| [52] | D. Zhuk, A proof of CSP dichotomy conjecture, in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, C. Umans, ed., Berkeley, CA, 2017, pp. 331-342. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
