Top

Theory of Computing Systems

Published in:

31-08-2021

The Complexity of Counting CSP^d

Author: Jiabao Lin

Published in: Theory of Computing Systems | Issue 1/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Counting CSP^d is the counting constraint satisfaction problem (# CSP in short) restricted to the instances where every variable occurs a multiple of d times. This paper revisits tractable structures in # CSP and gives a complexity classification theorem for # CSP^d with algebraic complex weights. The result unifies affine functions (stabilizer states in quantum information theory) and related variants such as the local affine functions, the discovery of which leads to all the recent progress on the complexity of Holant problems. The Holant is a framework that generalizes counting CSP. In the literature on Holant problems, weighted constraints are often expressed as tensors (vectors) such that projections and linear transformations help analyze the structure. This paper gives an example showing that different classes of constraints distinguished by these algebraic operations may share the same closure property.

previous article FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints

next article Stable Multi-Level Monotonic Eroders

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

In [4], a stronger condition called the Block Orthogonality is imposed on the set \(\mathcal {W}_{\mathcal {F}}\), but the algorithmic part of dichotomy only requires orthogonality. As we will see in Section 2, violation of the Orthogonality condition implies # P-hardness, which is proved by using the notion of block orthogonality.

For technical reasons, we require finite constraint languages in this paper. In fact, the equivalence also holds if we include equality functions of all arities.

Backens, M.: A New Holant Dichotomy Inspired by Quantum Computation. In: 44Th International Colloquium on Automata, Languages,And Programming, ICALP 2017, pp. 16:1–16:14. https://doi.org/10.4230/LIPIcs.ICALP.2017.16 (2017)

Backens, M.: A Complete Dichotomy for Complex-Valued Holant^c. In: 45Th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp. 12:1–12:14. https://doi.org/10.4230/LIPIcs.ICALP.2018.12 (2018)

Bulatov, A.A.: The complexity of the counting constraint satisfaction problem. J. ACM 60(5), 34 (2013). https://doi.org/10.1145/2528400MathSciNetMATH

Cai, J.Y., Chen, X.: Complexity of counting CSP with complex weights. J. ACM 64(3), 19:1–19:39 (2017). https://doi.org/10.1145/2822891MathSciNetCrossRef

Cai, J.Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. SIAM J. Comput. 42(3), 934–1029 (2013). https://doi.org/10.1137/110840194MathSciNetCrossRef

Cai, J.Y., Chen, X., Lu, P.: Nonnegative weighted #CSP: an effective complexity dichotomy. SIAM J. Comput. 45(6), 2177–2198 (2016). https://doi.org/10.1137/15m1032314MathSciNetCrossRef

Cai, J.Y., Fu, Z., Guo, H., Williams, T.: A Holant Dichotomy: Is the FKT Algorithm Universal?. In: IEEE 56Th Annual Symposium on Foundations of Computer Science, pp. 1259–1276. https://doi.org/10.1109/focs.2015.81 (2015)

Cai, J.Y., Fu, Z., Shao, S.: From Holant to Quantum Entanglement and Back. In: 47Th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbru̇cken, Germany (Virtual Conference), pp. 22:1–22:16. https://doi.org/10.4230/LIPIcs.ICALP.2020.22 (2020)

Cai, J.Y., Guo, H., Williams, T.: The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. In: 55Th IEEE Annual Symposium on Foundations of Computer Science, pp. 601–610. https://doi.org/10.1109/FOCS.2014.70 (2014)

10.

Cai, J.Y., Guo, H., Williams, T.: A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput. 45(5), 1671–1728 (2016). https://doi.org/10.1137/15m1049798MathSciNetCrossRef

11.

Cai, J.Y., Guo, H., Williams, T.: Clifford gates in the holant framework. Theor. Comput. Sci. 745, 163–171 (2018). https://doi.org/10.1016/j.tcs.2018.06.010MathSciNetCrossRef

12.

Cai, J.Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 715–724. https://doi.org/10.1145/1536414.1536511 (2009)

13.

Cai, J.Y., Lu, P., Xia, M.: Dichotomy for Holant^∗ problems with domain size 3. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1278–1295. https://doi.org/10.1137/1.9781611973105.93 (2013)

14.

Cai, J.Y., Lu, P., Xia, M.: The complexity of complex weighted Boolean #CSP. J. Comput. Syst. Sci. 80(1), 217–236 (2014). https://doi.org/10.1016/j.jcss.2013.07.003MathSciNetCrossRef

15.

Cai, J.Y., Lu, P., Xia, M.: Dichotomy for real Holant^c problems (2018)

16.

Dyer, M.E., Richerby, D.: An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput. 42(3), 1245–1274 (2013). https://doi.org/10.1137/100811258MathSciNetCrossRef

17.

Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336–3402 (2010). https://doi.org/10.1137/090757496MathSciNetCrossRef

18.

Huang, S., Lu, P.: A dichotomy for real weighted Holant problems. Comput. Complex. 25(1), 255–304 (2016). https://doi.org/10.1007/s00037-015-0118-3MathSciNetCrossRef

19.

Lin, J., Wang, H.: The complexity of Boolean Holant problems with nonnegative weights. SIAM J. Comput. 47(3), 798–828 (2018). https://doi.org/10.1137/17M113304XMathSciNetCrossRef

20.

Lovász, L.: Large Networks and Graph Limits, Colloquium Publications, vol. 60. American Mathematical Society. http://www.ams.org/bookstore-getitem/item=COLL-60 (2012)

21.

Shao, S., Cai, J.Y.: A dichotomy for real Boolean Holant problems To appear at FOCS (2020)

22.

Valiant, L.G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565–1594 (2008). https://doi.org/10.1137/070682575MathSciNetCrossRef

Title: The Complexity of Counting CSPd
Author: Jiabao Lin
Publication date: 31-08-2021
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 1/2022
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-021-10060-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2022

The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems

An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria

Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

Generating Visual Invariants −a New Approach to Invariant Recognition

FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints

Stable Multi-Level Monotonic Eroders

Premium Partner