Local holographic transformations: tractability and hardness

摘要

Local holographic transformations were introduced by Cai et al., and local affine functions, an extra tractable class, were derived by it in #CSP2. In the present paper, we not only generalize local affine functions to #CSPd 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.