Events at Physics |
In the statistical physics community there is a long history of research on Exactly Solved Models (Fisher, Temperley, Kasteleyn, C.N.Yang, Baxter, Lieb, ...). In the pure mathematics community Lovasz defined the general graph homomorphism functions in 1967.
There is a general sense that certain "systems" can be solved "exactly", while others are "difficult". There is also tremendous interest in certain "systems" which are "difficult" in general, but can be solved "exactly" on restricted classes of inputs. Fisher-Kasteleyn-Temperley method is a famous example.
All these predate the modern theory of computing, which is now guided by the P and NP conjecture. In the language of computational complexity theory, the FKT algorithm is a polynomial time algorithm for counting the number of perfect matchings for all planar graphs.
In this talk I report some exciting new development, coming from complexity theory. They give fairly general answers, in a provable sense, to the venerable question: What "systems" can be solved "exactly" and what "systems" are "difficult".