Research: Accidental Algorithms

Accidental Algorithms
American Scientist (02/08) Vol. 96, No. 1, P. 9; Hayes, Brian
"Holographic" or "accidental" algorithms comprise a new and unanticipated algorithmic family that offers efficient techniques for several problems whose solutions could only previously be worked out by brute-force computation. The algorithms facilitate deeper investigation into the barrier between P problems, which are problems with at least one polynomial-time algorithm, and nondeterministic polynomial (NP) problems. Within the NP class reside NP-complete problems, which stand out by virtue of having a polynomial-time solution that can be adapted to rapidly solve all problems in NP. Problems known to be NP-complete currently number in the thousands, and collectively they form a massive weave of interdependent computations. Harvard University's Leslie G. Valiant says holographic algorithms get their name from the fact that their computational power extends from the mutual cancellation of many contributions to a sum, much like the optical interference pattern responsible for generating a hologram. Holographic reductions tap a class of transformations that do not necessarily connect individual problem instances, but they do retain the number of solutions or the sum of the solutions. This is adequate for certain counting problems.
Click Here to View Full Article