Complexity: Knots, Colourings and Counting

ISBN-13: 9780521457408 / Angielski / Miękka / 1993 / 172 str.

D. J. A. Welsh

Opis

The aim of these notes is to link algorithmic problems arising in knot theory with statistical physics and classical combinatorics. Apart from the theory of computational complexity needed to deal with enumeration problems, introductions are given to several of the topics, such as combinatorial knot theory, randomized approximation models, percolation, and random cluster models.

Recenzje

"A clear and up-to-date survey of what's known--and what's still unknown." American Mathematical Monthly

Spis treści

1. The complexity of enumeration; 2. Knots and links; 3. Colourings, flows and polynomials; 4. Statistical physics; 5. Link polynomials; 6. Complexity questions; 7. The complexity of uniqueness and parity; 8. Approximation and randomisation; References.