Holographic algorithm

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduction</a> that maps solution fragments many-to-many such that the sum of the solution fragments remains unchanged. These concepts were introduced by <a href="/facts/Leslie_Valiant/hA5okAxL">Leslie Valiant</a>, who called them holographic because "their effect can be viewed as that of producing interference patterns among the solution fragments". The algorithms are unrelated to laser <a href="/facts/Holography/4J1gW0M6">holography</a>, except metaphorically. Their power comes from the mutual cancellation of many contributions to a sum, analogous to the interference patterns in a hologram.
Holographic algorithms have been used to find <a href="/facts/P_(complexity)/2TYvck4k">polynomial-time</a> solutions to problems without such previously known solutions for special cases of <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">satisfiability</a>, <a href="/facts/Vertex_cover/WK86bJvf">vertex cover</a>, and other <a href="/facts/Graph_theory/VVPCd4TX">graph problems</a>. They have received notable coverage due to speculation that they are relevant to the <a href="/facts/P_versus_NP_problem/xoC7Ruda">P versus NP problem</a> and their impact on <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>. Although some of the general problems are <a href="/facts/Sharp-P/tY95TU7t">#P-hard</a> problems, the special cases solved are not themselves #P-hard, and thus do not prove FP = #P.
Holographic algorithms have some similarities with <a href="/facts/Quantum_computation/nbbcgmvq">quantum computation</a>, but are completely classical.

Holographic algorithm open-in-new

Holographic algorithm