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:
“Women stand related to beautiful nature around us, and the enamoured youth mixes their form with moon and stars, with woods and waters, and the pomp of summer. They heal us of awkwardness by their words and looks. We observe their intellectual influence on the most serious student. They refine and clear his mind: teach him to put a pleasing method into what is dry and difficult.”
—Ralph Waldo Emerson (1803–1882)
“Then, bringing me the joy we feel when wee see a work by our favorite painter which differs from any other that we know, or if we are led before a painting of which we have until then only seen a pencil sketch, if a musical piece heard only on the piano appears before us clothed in the colors of the orchestra, my grandfather called me the [hawthorn] hedge at Tansonville, saying, “You who are so fond of hawthorns, look at this pink thorn, isn’t it lovely?””
—Marcel Proust (1871–1922)