http://sprott.physics.wisc.edu/chaos-complexity/12fall.html

September 11, 2012

Computational complexity theory --- The world of P and NP

Jin-Yi Cai, UW Department of Computer Sciences

Computational Complexity Theory is the study of intrinsic difficulties of computational problems. The most prominent open problem is the conjecture that P is not equal to NP.  In essense this conjecture states that it is intrinsically harder to find proofs than to verify them. It has a fundamental importance in many areas from computer science to mathematics, to our basic understanding of nature.

Valiant's new theory of holographic algorithms is one of the most beautiful ideas in algorithm design in recent memory.  It gives a new look on the P versus NP problem. In this theory, information is represented by a superposition of linear vectors in a holographic mix. This mixture creates the possibility for exponential sized cancellations of fragments of local computations. The underlying computation is done by invoking the Fisher-Kasteleyn-Temperley method for counting perfect matchings for planar graphs (Dimer Problem). Holographic algorithms challenge our conception of what polynomial time computation can do, in view of the P vs. NP question.

In this talk we will survey the developments in holographic algorithms. No specialized background is assumed.