Holographic algorithm

Holographic algorithms are a family of algorithms invented by Leslie ValiantHolographic Algorithms, by L. Valiant. In Proc. 45th IEEE Symposium onFoundations of Computer Science, 2004, 306-315.] that can obtain exponential speedup on certain classes of problems. These algorithms have received notable coverage due to speculation that they are relevant to the P=NP problem [http://www.americanscientist.org/issues/pub/accidental-algorithms Accidental Algorithms] : A strange new family of algorithms probes the boundary between easy and hard problems, by Brian Hayes, American Scientist, Jan-Feb 2008] and their impact on computational complexity theory. Holographic algorithms are also called 'accidental algorithms' due to their unlikely, capricious quality. 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. The algorithms have some similarities with quantum computation, but they use classical computation.

How the algorithms work

The algorithms are based on several concepts: counting perfect matchings, holographic reduction of sets of problems, and reduction to perfect matching problems.

The number of perfect matchings in a planar graph can be computed in polynomial time by using the FKT algorithm, dating to the 1960's. The FKT algorithm converts the problem into a Pfaffian computation, which can be solved polynomially using standard determinant algorithms. Note that although the basic formula for the determinant contains n! terms, the structure of the determinant allows it to be computed in polynomial time, as many terms cancel out and don't need to be computed. This cancellation is a key to holographic algorithms.

The second concept in holographic algorithms is reducing a problem to a different problem via holographic reduction. A standard technique in complexity is many-one reduction, so an instance of a problem is reduced to an instance of a (hopefully simpler) problem.However, holographic reductions between two computational problems preserve the sum of solutions without preserving correspondences between solutions. For instance, the total number of solutions in both sets can be preserved, even though individual problems don't have matching solutions. The sum can also be weighted, rather than simply counting the number of solutions, using linear basis vectors. [http://itcs.tsinghua.edu.cn/papers/2007/2007008.pdf Holographic Algorithms: From Art to Science] , by Jin-Yi Cai and Pinyan Lu, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007]

The holographic reduction uses "matchgates", which are graph-theoretic entities, analogous to logic gates, that use perfect matching to perform operations. The matchgates are combined into a planar graph called a "matchgrid". By Valiant's Holant Theorem, the (polynomial-time) perfect matching algorithm gives the solution to the matchgrid problem. Thus, the original problem is solved in polynomial time. [http://pages.cs.wisc.edu/~jyc/papers/HA-survey.pdf Holographic Algorithms] , Jin-Yi Cai]

Research

Holographic algorithms have been used to find polynomial solutions to problems without formerly-known polynomial solutions in satisfiability, vertex cover, and other graph problems. Although some of these problems are related to NP-complete problems, they are not themselves NP-complete, and thus do not prove P=NP. Also, some of the solved problems are argued to be contrived (such as '#₇Pl-Rtw-Mon-3CNF').

A key research area is extending holographic algorithms to new problems.

References