Holant Problems
Holographic algorithms exist in the context of Holant problems, which generalize counting constraint satisfaction problems (#CSP). A #CSP instance is a hypergraph G=(V,E) called the constraint graph. Each hyperedge represents a variable and each vertex is assigned a constraint A vertex is connected to an hyperedge if the constraint on the vertex involves the variable on the hyperedge. The counting problem is to compute
which is a sum over all variable assignments, the product of every constraint, where the inputs to the constrain are the variables on the incident hyperedges of .
A Holant problem is like a #CSP except the input must be a graph, not a hypergraph. Restricting the class of input graphs in this way is indeed a generalization. Given a #CSP instance, replace each hyperedge e of size s with a vertex v of degree s with edges incident to the vertices contained in e. The constraint on v is the equality function of arity s. This identifies all of the variables on the edges incident to v, which is the same effect as the single variable on the hyperedge e.
In the context of Holant problems, the expression in (1) is called the Holant after a related exponential sum introduced by Valiant.
Read more about this topic: Holographic Algorithm
Famous quotes containing the word problems:
“We are all adult learners. Most of us have learned a good deal more out of school than in it. We have learned from our families, our work, our friends. We have learned from problems resolved and tasks achieved but also from mistakes confronted and illusions unmasked. . . . Some of what we have learned is trivial: some has changed our lives forever.”
—Laurent A. Daloz (20th century)