Exponential Time Complexity of the Complex Weighted Boolean #CSP

Cai, Lu, and Xia [8] proved a dichotomy for complex weighted Boolean #CSP. If the parameter set of Boolean constraint functions $$\mathcal {F}$$ is a subset of either of the affine-type function set $$\mathcal {A}$$ and the product type function set $$\mathcal {P}$$ , then #CSP( $$\mathcal {F}$$ ) is polynomial-time solvable; otherwise, #CSP( $$\mathcal {F}$$ ) is #P-hard. Furthermore, the result holds for # $$R_3$$ -CSP( $$\mathcal {F}$$ ), which additionally restricts every variable constrained by no more than 3 constraint functions (not necessarily distinct). We strengthen the #P-hardness to the tight sub-exponential time lower bound under the counting Exponential Time Hypothesis (#ETH). We demonstrate that, if #ETH holds, then #CSP( $$\mathcal {F}$$ ) with $$\mathcal {F}\not \subseteq \mathcal {A}$$ and $$\mathcal {F}\not \subseteq \mathcal {P}$$ has no sub-exponential time algorithm. The result also holds for # $$R_D$$ -CSP( $$\mathcal {F}$$ ) with some integer $$D>0$$ , even $$D=3$$ . Additionally, we demonstrate that a vital tool pinning, forcing some variables to be 0 or 1, is still available in the context of # $$R_D$$ -CSP when proving the sub-exponential time lower bound.