On the Complexity of #CSP^d
summary
Proves a full dichotomy for Counting-CSP^d: for any finite function set F over a finite domain the partition function is computable in polynomial time exactly when the closure W_F^d satisfies three structural conditions, and otherwise the problem is #P‑hard by reductions from counting‑CSP (or suitable gadgeted CSP_G) and Holant‑style constructions. Uses complex‑valued weights, closure under variable summation and permutation to build algorithms, and a hardness path that leverages d‑occurrence restriction and standard CSP gadget reductions.
AI-written summary · about