History
As with any type of reduction, a holographic reduction does not, by itself, yield a polynomial time algorithm. In order to get a polynomial time algorithm, the problem being reduced to must also have 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, which he had just proved is tractable by a further reduction to counting the number of perfect matchings in a planar graph. 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. These problems may appear somewhat contrived, especially with respect to the modulus. Both problems were already known to be #P-hard when ignoring the modulus and Valiant supplied proofs of #P-hardness modulo 2, which also used holographic reductions. Valiant found these two problems by a computer search that looked for problems with holographic reductions to matchgates. He called their algorithms accidental algorithms, saying "when applying the term accidental to an algorithm we intend to point out that the algorithm arises from satisfying an apparently onerous set of constraints." 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. These two problem 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 the parameter k have holographic reductions to matchgates exactly when the modulus is the kth Mersenne number.
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. Instead, they reduced to a problem that is tractable by Fibonacci gates, which are symmetric constraints who's 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.
Read more about this topic: Holographic Algorithm
Famous quotes containing the word history:
“There is a constant in the average American imagination and taste, for which the past must be preserved and celebrated in full-scale authentic copy; a philosophy of immortality as duplication. It dominates the relation with the self, with the past, not infrequently with the present, always with History and, even, with the European tradition.”
—Umberto Eco (b. 1932)
“Regarding History as the slaughter-bench at which the happiness of peoples, the wisdom of States, and the virtue of individuals have been victimized—the question involuntarily arises—to what principle, to what final aim these enormous sacrifices have been offered.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“We know only a single science, the science of history. One can look at history from two sides and divide it into the history of nature and the history of men. However, the two sides are not to be divided off; as long as men exist the history of nature and the history of men are mutually conditioned.”
—Karl Marx (1818–1883)