Related Work
If the problem is to count the number of solutions, which is denoted by #CSP(Γ), then a similar result by Creignou and Hermann holds.
Let Γ be a finite constraint language over the Boolean domain. The problem #CSP(Γ) is computable in polynomial-time if Γ has a Mal'tsev operation as a polymorphism. Otherwise, the problem #CSP(Γ) is #P-complete.
A Mal'tsev operation m is a ternary operation that satisfies An example of a Mal'tsev operation is the Minority operation given in the modern, algebraic formulation of Schaefer's dichotomy theorem above. Thus, when Γ has the Minority operation as a polymorphism, it is not only possible to decide CSP(Γ) in polynomial-time, but to compute #CSP(Γ) in polynomial-time. Other examples of Mal'tsev operations include and
For larger domains, even for a domain of size three, the existence of a Mal'tsev polymorphism for Γ is no longer a sufficient condition for the tractability of #CSP(Γ). However, the absence of a Mal'tsev polymorphism for Γ still implies the #P-hardness of #CSP(Γ).
Read more about this topic: Schaefer's Dichotomy Theorem
Famous quotes containing the words related and/or work:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“In a world where women work three times as hard for half as much, our achievement has been denigrated, both marriage and divorce have turned against us, our motherhood has been used as an obstacle to our success, our passion as a trap, our empathy for others as an excuse to underpay us.”
—Erica Jong (20th century)