The Complexity of Counting CSPd

Counting CSPd is the counting constraint satisfaction problem (# CSP in short) restricted to the instances where every variable occurs a multiple of d times. This paper revisits tractable structures in # CSP and gives a complexity classification theorem for # CSPd with algebraic complex weights. The result unifies affine functions (stabilizer states in quantum information theory) and related variants such as the local affine functions, the discovery of which leads to all the recent progress on the complexity of Holant problems. The Holant is a framework that generalizes counting CSP. In the literature on Holant problems, weighted constraints are often expressed as tensors (vectors) such that projections and linear transformations help analyze the structure. This paper gives an example showing that different classes of constraints distinguished by these algebraic operations may share the same closure property.