MY AMERICAN SCIENTIST
SEARCH

COMPUTING SCIENCE

# Accidental Algorithms

A strange new family of algorithms probes the boundary between easy and hard problems

# P or NP, That Is the Question

Do holographic algorithms reveal anything we didn't already know about the P = NP question? Lest there be any misunderstanding, one point bears emphasizing: Although some of the problems solved by holographic methods were not previously known to be in P, none of them were NP-complete or #P-complete. Thus, so far, the barrier between P and NP remains intact.

Suggesting that P might be equal to NP is deeply unfashionable. A few years ago William Gasarch of the University of Maryland took a poll on the question. Of 100 respondents, only nine stood on the side of P = NP, and Gasarch reported that some of them took the position "just to be contrary." The idea that all NP problems have easy solutions seems too good to be true, an exercise in wishful thinking; it would be miraculous if we lived in a universe where computing is so effortless. But the miracle argument cuts both ways: For NP to remain aloof from P, we have to believe that not even one out of all those thousands of NP-complete problems has an efficient solution.

Valiant suggests a comparison with the Goldbach conjecture, which holds that every even number greater than 2 is the sum of two primes. Nearly everyone believes it to be true, but in the absence of a proof, we don't know why it should be true. We can't rule out the possibility that exceptions exist but are so rare we haven't stumbled on one yet. Likewise with the P and NP question: A polynomial algorithm for just one NP-complete problem would forever alter the landscape.

The work on holographic algorithms doesn't have to be seen as some sort of wildcat drilling expedition, hoping to strike a P = NP gusher. It would be worthwhile just to have a finer survey of the boundaries between complexity classes, showing more clearly what can and can't be accomplished with polynomial resources. Valiant writes that "any proof of P ? NP will need to explain, and not only to imply, the unsolvability of our polynomial systems."

Finally, there's the challenge of understanding the algorithms themselves at a deeper level. To call them "accidental"—or "exotic," or "freak," which are other terms that turn up in the literature—suggests that they are sports of nature, like weird creatures found under a rock and put on exhibit. But one could also argue, on the contrary, that these algorithms are not at all accidental; they are highly engineered constructions. The elaborate systems of polynomials needed to create sets of matchgates are not something found in the primordial ooze of mathematics. Someone had to invent them.

# Bibliography

• Cai, Jin-Yi. Preprint. Holographic algorithms. http://pages.cs.wisc.edu/~jyc/papers/HA-survey.pdf.
• Cai, Jin-Yi, Vinay Choudhary and Pinyan Lu. 2007. On the theory of matchgate computations. In Proceedings of the 22nd IEEE Conference on Computational Complexity, pp. 305-318.
• Cai, Jin-Yi, and Pinyan Lu. 2007. Holographic algorithms: From art to science. In Proceedings of the 39th ACM Symposium on the Theory of Computing, STOC '07, pp. 401-410.
• Cai, Jin-Yi, and Pinyan Lu. 2007. Holographic algorithms: The power of dimensionality resolved. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, pp. 631-642.
• Cook, Stephen A. 1971. The complexity of theorem-proving procedures. In Proceedings of the Third ACM Symposium on the Theory of Computing, pp. 151-158.
• Edmonds, Jack. 1965. Paths, trees, and flowers. Canadian Journal of Mathematics 17:449-467.
• Gasarch, William I. 2002. The P=?NP poll. SIGACT News 33(2):34-47.
• Jerrum, Mark. 2003. Counting, Sampling and Integrating: Algorithms and Complexity. Basel, Switzerland: Birkhauser.
• Kasteleyn, P. W. 1961. The statistics of dimers on a lattice. Physica 27:1209-1225.
• Mertens, Stephan. 2002. Computational complexity for physicists. Computing in Science and Engineering 4(3):31-47.
• Valiant, L. G. 1979. The complexity of computing the permanent. Theoretical Computer Science 8:189-201.
• Valiant, Leslie G. 2002. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing 31:1229-1254.
• Valiant, Leslie G. 2005. Holographic algorithms. Electronic Colloquium on Computational Complexity, Report No. 99.l
• Valiant, Leslie G. 2006. Accidental algorithms. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, FOCS '06, pp. 509-517.