## Algebrization: A New Barrier in Complexity Theory

From: "andrew cooke" <andrew@...>

Date: Sat, 3 May 2008 08:28:56 -0400 (CLT)

I don't understand this completely, but it's very interesting.  There's a
relationship between communication complexity (information theory) and the
difference between P and NP.  At the same time (not covered here, but I
guess I've mentioned it elsewhere), information theory is somehow
connected with quantum mechanics.  It seems that there's something "deep"
about information and how our world works.

http://eccc.hpi-web.de/eccc-reports/2008/TR08-005/index.html

From the guy at http://complexityzoo.com (which has a section on quantum
information http://qwiki.stanford.edu/wiki/Category:Quantum_Information )

Andrew