Holographic Algorithm

Holographic algorithms are a class of algorithms, introduced by Leslie Valiant and presented at the IEEE Symposium on Foundations of Computer Science in October 2004, that use what Valiant called holographic reductions, constant-time reductions that map fragments of a solution to a problem in a many-to-many fashion while preserving the total sum of solutions. Their computational power comes from the mutual cancellation of many contributing terms in that sum, an effect Valiant compared to the interference patterns formed in an optical hologram, even though the algorithms themselves are entirely classical rather than quantum. Holographic algorithms have produced polynomial-time solutions to special cases of problems, including certain satisfiability and vertex-cover problems, that previously had no known polynomial-time algorithm, and have drawn substantial academic interest for their possible bearing on the P versus NP question, although the specific problem instances they solve are not themselves sharp-P-hard, so they do not settle whether FP equals sharp-P. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/