The complexity of enumeration / 1: |
Basics of complexity / 1.1: |
Counting problems / 1.2: |
# P-complete problems / 1.3: |
Decision easy, counting hard / 1.4: |
The Permanent / 1.5: |
Hard enumeration problems not thought to be #P-complete / 1.6: |
Self-avoiding walks / 1.7: |
Toda's theorems / 1.8: |
Additional notes / 1.9: |
Knots and links / 2: |
Introduction / 2.1: |
Tait colourings / 2.2: |
Classifying knots / 2.3: |
Braids and the braid group / 2.4: |
The braid index and the Seifert graph of a link / 2.5: |
Enzyme action / 2.6: |
The number of knots and links / 2.7: |
The topology of polymers / 2.8: |
Colourings, flows and polynomials / 2.9: |
The chromatic polynomial / 3.1: |
The Whitney-Tutte polynomials / 3.2: |
Tutte Grothendieck invariants / 3.3: |
Reliability theory / 3.4: |
Flows over an Abelian group / 3.5: |
Ice models / 3.6: |
A catalogue of invariants / 3.7: |
Statistical physics / 3.8: |
Percolation processes / 4.1: |
The Ising model / 4.2: |
Combinatorial interpretations / 4.3: |
The Ashkin-Teller-Potts model / 4.4: |
The random cluster model / 4.5: |
Percolation in the random cluster model / 4.6: |
Link polynomials and the Tait conjectures / 4.7: |
The Alexander polynomial / 5.1: |
The Jones polynomial and Kauffman bracket / 5.2: |
The Homfly polynomial / 5.3: |
The Kauffman 2-variable polynomial / 5.4: |
The Tait conjectures / 5.5: |
Thistlethwaite's nontriviality criterion / 5.6: |
Link invariants and statistical mechanics / 5.7: |
Complexity questions / 5.8: |
Computations in knot theory / 6.1: |
The complexity of the Tutte plane / 6.2: |
The complexity of knot polynomials / 6.3: |
The complexity of the Ising model / 6.4: |
Reliability and other computations / 6.5: |
The complexity of uniqueness and parity / 6.6: |
Unique solutions / 7.1: |
Unambiguous machines and one-way functions / 7.2: |
The Valiant-Vazirani theorem / 7.3: |
Hard counting problems not parsimonious with SAT / 7.4: |
The curiosity of parity / 7.5: |
Toda's theorem on parity / 7.6: |
Approximation and randomisation / 7.7: |
Metropolis methods / 8.1: |
Approximating to within a ratio / 8.2: |
Generating solutions at random / 8.3: |
Rapidly mixing Markov chains / 8.4: |
Computing the volume of a convex body / 8.5: |
Approximations and the Ising model / 8.6: |
Some open questions / 8.7: |
References / 8.8: |
The complexity of enumeration / 1: |
Basics of complexity / 1.1: |
Counting problems / 1.2: |