| |
| |
| |
| The complexity of enumeration | |
| |
| |
| |
| Basics of complexity | |
| |
| |
| |
| Counting problems | |
| |
| |
| |
| # P-complete problems | |
| |
| |
| |
| Decision easy, counting hard | |
| |
| |
| |
| The Permanent | |
| |
| |
| |
| Hard enumeration problems not thought to be #P-complete | |
| |
| |
| |
| Self-avoiding walks | |
| |
| |
| |
| Toda's theorems | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| Knots and links | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Tait colourings | |
| |
| |
| |
| Classifying knots | |
| |
| |
| |
| Braids and the braid group | |
| |
| |
| |
| The braid index and the Seifert graph of a link | |
| |
| |
| |
| Enzyme action | |
| |
| |
| |
| The number of knots and links | |
| |
| |
| |
| The topology of polymers | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| Colourings, flows and polynomials | |
| |
| |
| |
| The chromatic polynomial | |
| |
| |
| |
| The Whitney-Tutte polynomials | |
| |
| |
| |
| Tutte Grothendieck invariants | |
| |
| |
| |
| Reliability theory | |
| |
| |
| |
| Flows over an Abelian group | |
| |
| |
| |
| Ice models | |
| |
| |
| |
| A catalogue of invariants | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| Statistical physics | |
| |
| |
| |
| Percolation processes | |
| |
| |
| |
| The Ising model | |
| |
| |
| |
| Combinatorial interpretations | |
| |
| |
| |
| The Ashkin-Teller-Potts model | |
| |
| |
| |
| The random cluster model | |
| |
| |
| |
| Percolation in the random cluster model | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| Link polynomials and the Tait conjectures | |
| |
| |
| |
| The Alexander polynomial | |
| |
| |
| |
| The Jones polynomial and Kauffman bracket | |
| |
| |
| |
| The Homfly polynomial | |
| |
| |
| |
| The Kauffman 2-variable polynomial | |
| |
| |
| |
| The Tait conjectures | |
| |
| |
| |
| Thistlethwaite's nontriviality criterion | |
| |
| |
| |
| Link invariants and statistical mechanics | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| Complexity questions | |
| |
| |
| |
| Computations in knot theory | |
| |
| |
| |
| The complexity of the Tutte plane | |
| |
| |
| |
| The complexity of knot polynomials | |
| |
| |
| |
| The complexity of the Ising model | |
| |
| |
| |
| Reliability and other computations | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| The complexity of uniqueness and parity | |
| |
| |
| |
| Unique solutions | |
| |
| |
| |
| Unambiguous machines and one-way functions | |
| |
| |
| |
| The Valiant-Vazirani theorem | |
| |
| |
| |
| Hard counting problems not parsimonious with SAT | |
| |
| |
| |
| The curiosity of parity | |
| |
| |
| |
| Toda's theorem on parity | |
| |
| |
| |
| Additional notes | |
| |
| |
| |
| Approximation and randomisation | |
| |
| |
| |
| Metropolis methods | |
| |
| |
| |
| Approximating to within a ratio | |
| |
| |
| |
| Generating solutions at random | |
| |
| |
| |
| Rapidly mixing Markov chains | |
| |
| |
| |
| Computing the volume of a convex body | |
| |
| |
| |
| Approximations and the Ising model | |
| |
| |
| |
| Some open questions | |
| |
| |
| |
| Additional notes | |
| |
| |
| References | |