Local holographic transformations:tractability and hardness  

作　　者：Peng YANG Zhiguo FU 

机构地区：[1]School of Information Science and Technology&KLAS,Northeast Normal University,Changchun 130117,China

出　　处：《Frontiers of Computer Science》2023年第2期167-177,共11页中国计算机科学前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant No.61872076);the Natural Science Foundation of Jilin Province(20200201161JC).

摘　　要：Local holographic transformations were introduced by Cai et al.,and local affine functions,an extra tractable class,were derived by it in#CSP^(2).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.

关 键 词：#CSP^(d) Holant problems local holographic transformations 

分 类 号：O43[机械工程—光学工程]