6. Classification Theorems for Decision, Counting and Quantified Problems
Society for Industrial and Applied Mathematics eBooks · 2001
We now study the complexity of the decision, counting and quantified variants of the constraint satisfaction problems. We will show that each of these classes exhibits a dichotomy — any problem in each of these classes is either “easy” or at least as “hard” as any other problem in the corresponding class. Such dichotomy results are a rare phenomenon in the study of complexity theory. Our proof techniques build on the results of the preceding chapter; we will show that our implementation lemmas give simple proofs for these dichotomy theorems. While the dichotomy result for the decision and counting problems were previously known, the dichotomy result for the quantified constraint satisfaction problems is new. 6.1 Preliminaries To reduce a problem SAT(ℱ ) (#SAT(ℱ )) to a problem SAT(ℱ ′) (#SAT(ℱ ′)), we will often use SAT(ℱ ′ ∪ {F, T}) (#SAT(ℱ ′ ∪ {F, T})) as an intermediate problem. We will show that for our purposes, the functions F and T can be easily implemented, provided the family ℱ ′ is not C-closed. However, it is not possible to do so when the family ℱ ′ is C-closed. In this particular case we will use the following lemma. Lemma 6.1 Let ℱ be a set of C-closed constraints. If SAT(ℱ ∪{F, T}) is NP-hard (P-hard) and if ℱ can perfectly implement the XOR function, then SAT(ℱ ) is NP-hard (P-hard). If #SAT( ℱ ∪ {F, T}) ) is #P-hard and if ℱ can faithfully implement the XOR function, then #SAT(ℱ ) is #P-hard. Proof: First we show a log-space (counting) reduction from SAT(ℱ ∪ {F,T}) (#SAT(ℱ ∪ {F, T})) to SAT(ℱ ∪ {XOR}) (#SAT(ℱ ∪ {XOR})). It suffices to use two new variables, x0 and x1, that will simulate the role of functions F and T. Let C be an ℱ ∪ {F, T}-collection of constraint applications on variables . We use the variable x0 in place of any variable y with the constraint F(y) and the variable x1 in place of any variable z with the constraint T(z). Next we add the constraint XOR( x0, x1). We get C ′, an ℱ ∪ {XOR}-collection of constraint applications on variables , x0, x1.