Local holographic transformations: tractability and hardness

Abstract

Local holographic transformations were introduced by Cai et al., and local affine functions, an extra tractable class, were derived by it in #CSP². In the present paper, we not only generalize local affine functions to #CSP^d for general d, but also give new tractable classes by combining local holographic transformations with global holographic transformations. Moreover, we show how to use local holographic transformations to prove hardness. This is of independent interests in the complexity classification of counting problems.

Graphical abstract

Keywords

#CSP^d / Holant problems / local holographic transformations

Peng Yang is currently a PhD student in the School of Information Science and Technology, Northeast Normal University, China. His currently research interests include computational complexity of counting problems

Zhiguo Fu received the PhD degree in the school of Mathematics from Jilin University, China. He is an associate professor and doctoral supervisor at Northeast Normal University, China. His research interests lie in theoretical computer science

References

[1] Valiant L G . Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 2002, 31( 4): 1229– 1254

[2] Valiant L G . Holographic algorithms. SIAM Journal on Computing, 2008, 37( 5): 1565– 1594

[3] Kasteleyn P W . The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 1961, 27( 12): 1209– 1225

[4] Harary F . Graph Theory and Theoretical Physics. London: Academic Press, 1967, 43– 110

[5] Temperley H N V , Fisher M E . Dimer problem in statistical mechanics- an exact result. The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics, 1961, 6( 68): 1061– 1063

[6] Valiant L G. Accidental algorthims. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. 2006, 509– 517

[7] Bulatov A , Dyer M , Goldberg L A , Jalsenius M , Jerrum M , Richerby D . The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences, 2012, 78( 2): 681– 688

[8] Backens M. A complete dichotomy for complex-valued holant^c. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. 2018, 1– 14

[9] Cai J Y , Chen X , Lu P . Graph homomorphisms with complex values: a dichotomy theorem. SIAM Journal on Computing, 2013, 42( 3): 924– 1029

[10] Cai J Y, Guo H, Williams T. A complete dichotomy rises from the capture of vanishing signatures. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 2013, 635– 644

[11] Cai J Y , Lu P , Xia M . The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 2014, 80( 1): 217– 236

[12] Cai J Y, Fu Z, Guo H, Williams T. A holant dichotomy: is the FKT algorithm universal? In: Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science. 2015, 1259− 1276

[13] Cai J Y , Chen X , Lu P . Nonnegative weighted #CSP: an effective complexity dichotomy. SIAM Journal on Computing, 2016, 45( 6): 2177– 2198

[14] Cai J Y , Chen X . Complexity of counting CSP with complex weights. Journal of the ACM, 2017, 64( 3): 19

[15] Cai J Y, Fu Z. Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 2017, 842– 855

[16] Lin J , Wang H . The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 2018, 47( 3): 798– 828

[17] Shao S, Cai J Y. A dichotomy for real Boolean holant problems. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science. 2020, 1091− 1102

[18] Huang S , Lu P . A dichotomy for real weighted holant problems. Computational Complexity, 2016, 25( 1): 255– 304

[19] Cai J Y, Lu P, Xia M. Dichotomy for real holant^c problems . In: Proceedings of 2018 Annual ACM-SIAM Symposium on Discrete Algorithms. 2018, 1802− 1821

[20] Lin J B. The complexity of counting CSP^d. Theory of Computing Systems, 2021, 65(6): 1− 13

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 61872076) and the Natural Science Foundation of Jilin Province (20200201161JC).

RIGHTS & PERMISSIONS

2023 Higher Education Press