A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains unchanged.
These concepts were introduced by Leslie Valiant, who called them holographic because "their effect can be viewed as that of producing interference patterns among the solution fragments".
[1] The algorithms are unrelated to laser holography, except metaphorically.
Their power comes from the mutual cancellation of many contributions to a sum, analogous to the interference patterns in a hologram.
[2] Holographic algorithms have been used to find polynomial-time solutions to problems without such previously known solutions for special cases of satisfiability, vertex cover, and other graph problems.
[3] They have received notable coverage due to speculation that they are relevant to the P versus NP problem[2] and their impact on computational complexity theory.
Although some of the general problems are #P-hard problems, the special cases solved are not themselves #P-hard, and thus do not prove FP = #P. Holographic algorithms have some similarities with quantum computation, but are completely classical.
A #CSP instance is a hypergraph G=(V,E) called the constraint graph.
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
A Holant problem is like a #CSP except the input must be a graph, not a hypergraph.
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.
[5] A standard technique in complexity theory is a many-one reduction, where an instance of one problem is reduced to an instance of another (hopefully simpler) problem.
The sum can also be weighted, rather than simply counting the number of solutions, using linear basis vectors.
[3] It is convenient to consider holographic reductions on bipartite graphs.
To keep the same Holant value, each new vertex is assigned the binary equality constraint.
Consider a bipartite graph G=(U,V,E) where the constraint assigned to every vertex
be represented by its weighted truth table as a row vector and the constraint
be represented by its weighted truth table as a column vector.
Now for any complex 2-by-2 invertible matrix T (the columns of which are the linear basis vectors mentioned above), there is a holographic reduction between
the Holant problem that naturally corresponds to counting the number of independent sets in G. As with any type of reduction, a holographic reduction does not, by itself, yield a polynomial time algorithm.
Valiant's original application of holographic algorithms used a holographic reduction to a problem where every constraint is realizable by matchgates,[1] which he had just proved is tractable by a further reduction to counting the number of perfect matchings in a planar graph.
[6] The latter problem is tractable by the FKT algorithm, which dates to the 1960s.
Soon after, Valiant found holographic algorithms with reductions to matchgates for #7Pl-Rtw-Mon-3CNF and #7Pl-3/2Bip-VC.
The "onerous" set of constraints in question are polynomial equations that, if satisfied, imply the existence of a holographic reduction to matchgate realizable constraints.
After several years of developing (what is known as) matchgate signature theory, Jin-Yi Cai and Pinyan Lu were able to explain the existence of Valiant's two accidental algorithms.
[3] These two problems are just special cases of two much larger families of problems: #2k-1Pl-Rtw-Mon-kCNF and #2k-1Pl-k/2Bip-VC for any positive integer k. The modulus 7 is just the third Mersenne number and Cai and Lu showed that these types of problems with parameter k can be solved in polynomial time exactly when the modulus is the kth Mersenne number by using holographic reductions to matchgates and the Chinese remainder theorem.
Around the same time, Jin-Yi Cai, Pinyan Lu and Mingji Xia gave the first holographic algorithm that did not reduce to a problem that is tractable by matchgates.
[5] Instead, they reduced to a problem that is tractable by Fibonacci gates, which are symmetric constraints whose truth tables satisfy a recurrence relation similar to one that defines the Fibonacci numbers.
They also used holographic reductions to prove that certain counting problems are #P-hard.
Since then, holographic reductions have been used extensively as ingredients in both polynomial time algorithms and proofs of #P-hardness.