The Complexity of Weighted Boolean #CSP Modulo k

Heng Guo, Sangxia Huang, Pinyan Lu, Mingji XiaSTACS 2011 · OpenReview

TL;DR

This paper tackles the complexity of counting solutions to a specific type of computational problem called Weighted Boolean #CSP, but with a twist: the counting is done modulo an integer $k$. The authors establish a "dichotomy theorem," meaning they precisely classify all such problems as either efficiently solvable (in polynomial time) or computationally intractable (harder than NP). This work generalizes previous results and reveals new tractable problems in the weighted setting.

What Problem Does This Paper Address?

Computational complexity theory often seeks to understand which problems can be solved efficiently by computers. The class of problems known as #CSP (Counting Satisfiability Problems) involves counting the number of ways to assign values to variables to satisfy a set of constraints. This paper focuses on a more general version: Weighted Boolean #CSP Modulo k.

Here's a breakdown:

  • Boolean: The variables can only take values 0 or 1.
  • CSP: The problem involves constraints defined by functions that map Boolean inputs to integer outputs.
  • Weighted: The functions can output arbitrary integer values, not just 0 or 1.
  • Modulo k: The final count of solutions is not the exact number, but its remainder when divided by an integer $k$.

The challenge is to find a complete classification of these problems. Previous work by Faben established such a classification for the unweighted case (where functions output only 0 or 1). However, introducing weights and the modulo operation complicates things significantly. The authors aim to provide a comprehensive understanding of the computational landscape for these weighted #CSP problems modulo $k$.

Methods

The paper employs a variety of sophisticated techniques from theoretical computer science and algebra. Key among them are:

  • Dichotomy Theorems: The core of the paper is proving a dichotomy theorem. This involves showing that for a given class of problems, every problem within that class falls into one of two categories: tractable (solvable efficiently) or #P-hard (computationally intractable).
  • Algebraic Techniques: The authors leverage algebraic structures, particularly working within finite fields (like $\mathbb{Z}_p$ for prime $p$) and rings ($\mathbb{Z}_k$). Concepts like quadratic residues and roots of unity play a crucial role.
  • Reductions: To prove hardness, they use reductions. This means showing that if a problem were solvable efficiently, then a known hard problem could also be solved efficiently, which is a contradiction.
  • Gadget Constructions: These are clever ways to construct new computational problems from existing ones, often used to simulate specific functions or properties.
  • Holographic Transformations and Polynomial Interpolation (and their limitations): These are powerful tools in complexity theory, particularly for counting problems. The paper discusses how these techniques, while successful in related areas (like complex-valued #CSP), are not directly applicable in finite fields due to their algebraic properties.
  • Chinese Remainder Theorem: This fundamental theorem of number theory is used to extend results from prime moduli to composite moduli.

Datasets

Not discussed in the paper. This paper is theoretical and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Generalization of Unweighted Results: The paper successfully extends the dichotomy theorem for unweighted #CSP to the weighted case modulo $k$. This is a significant step in understanding the complexity of counting problems.
  • New Tractable Problems Emerge: Unlike the unweighted case, introducing weights leads to new classes of problems that are surprisingly tractable. This highlights how adding complexity (weights) can sometimes simplify the computational landscape by enabling new algorithmic approaches.
  • Finite Fields vs. Complex Numbers: The paper draws parallels and contrasts between computations in finite fields (like $\mathbb{Z}_p$) and computations with complex numbers. While some algebraic similarities exist, key techniques like polynomial interpolation behave differently, requiring novel approaches.
  • The Role of Modulus $k$: The nature of the modulus $k$ (prime vs. composite, power of 2 vs. odd prime power) significantly impacts the complexity. The paper meticulously handles these different cases.
  • The "Dichotomy" is Sharp: The paper provides a precise characterization: every weighted #CSP modulo $k$ is either in P (polynomial time) or #pP-hard for some prime $p$ dividing $k$. This leaves no ambiguity about the computational status of these problems.

Key Results

The main result is a comprehensive complexity dichotomy theorem for weighted Boolean #CSP modulo $k$. Specifically:

  • For any positive integer $k > 1$ and any set of constraint functions $F$, the problem $\#kCSP(F)$ is either solvable in polynomial time (P) or is $\#pP$-hard for some prime $p$ that divides $k$.
  • The paper first establishes this dichotomy for prime moduli $k=p$, showing it's closely related to the complexity of complex-valued #CSP.
  • It then extends this result to arbitrary integers $k$ using the Chinese Remainder Theorem.
  • The paper identifies specific classes of functions that lead to tractable problems, particularly when weights are introduced.

Limitations and Future Work

  • Technical Complexity: The paper acknowledges that the statement of the main theorem (Theorem 19) is "a little complicated due to technique reason." This suggests that the precise conditions for tractability, especially when $k$ is a power of 2, are intricate.
  • Comparison to Unweighted Case: The authors note that their dichotomy for weighted #CSP modulo $k$ is "slightly different" from Faben's result for the unweighted case, particularly concerning the conditions for different odd primes. This difference stems from the new tractable cases introduced by weights.
  • Future Work: The paper's conclusion implies that the established dichotomy provides a solid foundation for future research in this area. The detailed classification opens doors for exploring the specific algorithms for the tractable cases and further understanding the boundary between P and #P-hard for related counting problems. The paper also hints at the need for specialized treatments for the case $k=2$.

Summary updated

Abstract

We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer $k>1$. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k.
BibTeX
@inproceedings{guo2011complexity,
  author = {Heng Guo and Sangxia Huang and Pinyan Lu and Mingji Xia},
  title = {{The Complexity of Weighted Boolean \#CSP Modulo k}},
  booktitle = {STACS},
  year = {2011},
  url = {https://openreview.net/forum?id=JDOlns0wbG},
}
Figure