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#C...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.展开更多
基金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.
