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.