\n

\nIn the statistical physics community there is a long history of res earch on Exactly Solved Models (Fisher\, Temperley\, Kasteleyn\, C.N.Y ang\, Baxter\, Lieb\, ...). In the pure mathematics community Lovasz d efined the general graph homomorphism functions in 1967.

\n

\n 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 solve d "exactly" on restricted classes of inputs. Fisher-Kasteleyn-Temperle y method is a famous example.

\n

\nAll these predate the moder n theory of computing\, which is now guided by the P and NP conjecture . In the language of computational complexity theory\, the FKT algorit hm is a polynomial time algorithm for counting the number of perfect m atchings for all planar graphs.

\n

\nIn this talk I report som e exciting new development\, coming from complexity theory. They give fairly general answers\, in a provable sense\, to the venerable questi on: What "systems" can be solved "exactly" and what "systems" are "dif ficult". URL:https://www.physics.wisc.edu/events/?id=1820 END:VEVENT END:VCALENDAR