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:
“A parent who from his own childhood experience is convinced of the value of fairy tales will have no difficulty in answering his child’s questions; but an adult who thinks these tales are only a bunch of lies had better not try telling them; he won’t be able to related them in a way which would enrich the child’s life.”
—Bruno Bettelheim (20th century)
“Working women today are trying to achieve in the work world what men have achieved all along—but men have always had the help of a woman at home who took care of all the other details of living! Today the working woman is also that woman at home, and without support services in the workplace and a respect for the work women do within and outside the home, the attempt to do both is taking its toll—on women, on men, and on our children.”
—Jeanne Elium (20th century)