Local holographic transformations: tractability and hardness

doi:10.1007/s11704-022-1231-5

Front. Comput. Sci.

2023, Vol. 17

Issue (2) : 172401 https://doi.org/10.1007/s11704-022-1231-5

RESEARCH ARTICLE

Local holographic transformations: tractability and hardness

Peng YANG, Zhiguo FU(

)

School of Information Science and Technology & KLAS, Northeast Normal University, Changchun 130117, China

Download: PDF(1375 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords #CSP^d Holant problems local holographic transformations

Corresponding Author(s): Zhiguo FU

Just Accepted Date: 28 September 2021 Issue Date: 07 July 2022

Cite this article:

Peng YANG,Zhiguo FU. Local holographic transformations: tractability and hardness[J]. Front. Comput. Sci., 2023, 17(2): 172401.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-1231-5
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I2/172401

Fig.1 An

F

-gate with five dangling edges

Fig.2 The circle vertices are assigned

(0, 1, γ, 0)

, the squares are assigned

(= 4)

, the triangles are assigned

(0, γ, 1, 0)

, and the diamond is assigned

(= 4 k)

. (a) Realizing

ε

Q4 on the right side; (b) Realizing (0, 1, γ, 0) on the left side

Fig.3 Realizing

(0, 1, γ 3, 0)

on the right side. The circle vertices are assigned

(0, 1, γ, 0)

and the squares are assigned

(= 4)

Fig.4 Realizing

f 10

on the right side. The star vertex is assigned

f 4

, diamond vertices are assigned

(1, 0, …, 0, γ 4)

, square vertices are assigned

(= 4)

, and circle vertices are assigned

x 1, x 2

x 12 = x 1 + x 2

1	L G Valiant . Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 2002, 31( 4): 1229– 1254
2	L G Valiant . Holographic algorithms. SIAM Journal on Computing, 2008, 37( 5): 1565– 1594
3	P W Kasteleyn . The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 1961, 27( 12): 1209– 1225
4	F Harary . Graph Theory and Theoretical Physics. London: Academic Press, 1967, 43– 110
5	H N V Temperley , M E Fisher . 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	L G Valiant. Accidental algorthims. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. 2006, 509– 517
7	A Bulatov , M Dyer , L A Goldberg , M Jalsenius , M Jerrum , D Richerby . The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences, 2012, 78( 2): 681– 688
8	M Backens. A complete dichotomy for complex-valued holantc. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. 2018, 1– 14
9	J Y Cai , X Chen , P Lu . Graph homomorphisms with complex values: a dichotomy theorem. SIAM Journal on Computing, 2013, 42( 3): 924– 1029
10	J Y Cai, H Guo, T Williams. 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	J Y Cai , P Lu , M Xia . The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 2014, 80( 1): 217– 236
12	J Y Cai, Z Fu, H Guo, T Williams. 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	J Y Cai , X Chen , P Lu . Nonnegative weighted #CSP: an effective complexity dichotomy. SIAM Journal on Computing, 2016, 45( 6): 2177– 2198
14	J Y Cai , X Chen . Complexity of counting CSP with complex weights. Journal of the ACM, 2017, 64( 3): 19
15	J Y Cai, Z Fu. 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	J Lin , H Wang . The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 2018, 47( 3): 798– 828
17	S Shao, J Y Cai. A dichotomy for real Boolean holant problems. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science. 2020, 1091− 1102
18	S Huang , P Lu . A dichotomy for real weighted holant problems. Computational Complexity, 2016, 25( 1): 255– 304
19	J Y Cai, P Lu, M Xia. Dichotomy for real holantc problems . In: Proceedings of 2018 Annual ACM-SIAM Symposium on Discrete Algorithms. 2018, 1802− 1821
20	J B Lin. The complexity of counting CSPd. Theory of Computing Systems, 2021, 65(6): 1− 13

Viewed

Full text

Abstract

Cited

Shared

Discussed