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:
“Perhaps it is nothingness which is real and our dream which is non-existent, but then we feel think that these musical phrases, and the notions related to the dream, are nothing too. We will die, but our hostages are the divine captives who will follow our chance. And death with them is somewhat less bitter, less inglorious, perhaps less probable.”
—Marcel Proust (1871–1922)
“A tremendous number of people in America work very hard at something that bores them. Even a rich man thinks he has to go down to the office every day. Not because he likes it but because he can’t think of anything else to do.”
—W.H. (Wystan Hugh)