Holographic algorithm
Holographic algorithms are a family of algorithms invented by Leslie Valiant[1] 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[2] and their impact on computational complexity theory. Holographic algorithms are also called 'accidental algorithms' due to their unlikely, capricious quality.[2] The algorithms are unrelated to laser holography.
How the algorithms work
 | This article needs attention from an expert in computer science. Please add a reason or a talk parameter to this template to explain the issue with the article. |
Holographic algorithms perform computation through a choice of linear basis vectors in an exponential "holographic" mix, and then use the FKT perfect matching method via the Holant Theorem, using a polynomial-time algorithm for evaluating Pfaffians.[3] The algorithms are based on holographic reductions between two computational problems, which preserve the sum of solutions without preserving correspondences between solutions.[1]
American Scientist gives a simplified overview of the algorithm.[2]
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.[3] Although some of these problems are related to NP-complete problems, they are not themselves NP-complete, and thus do not prove P=NP.[3] Also, some of the solved problems are argued to be contrived (such as '#7Pl-Rtw-Mon-3CNF').[3]
References
- ^ a b Holographic Algorithms, by L. Valiant. In Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004, 306–315.
- ^ a b c Accidental Algorithms: A strange new family of algorithms probes the boundary between easy and hard problems, by Brian Hayes, American Scientist, Jan-Feb 2008
- ^ a b c d 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
 | This computer science article is a stub. You can help Wikipedia by expanding it. |