Counting worlds

Deciding whether a network of knots allows any world can be easy while counting its worlds is hard. Two notes in this repository locate where counting turns hard.

Counting words. The words used for counting follow lesson 4.1. A world here is an allowed state, as in lesson 4.2.

• #P ("sharp P") is the class of counting questions whose objects are easy to check, such as how many states a CNF allows, or how many perfect matchings a graph has (ways of pairing up all its vertices along its edges). A counting question is #P-hard when every question in #P translates into it. A polynomial-time method for a #P-hard count would also decide every question in NP quickly, so none is expected.
• Counting can be hard when deciding is easy. Deciding a 2-CNF takes linear time, but counting the states it allows is #P-hard; deciding whether a graph has a perfect matching takes polynomial time (Edmonds 1965), but counting its perfect matchings is #P-hard. Classical: Valiant 1979.
• Planar graphs are the classical exception. On a graph drawn in the plane without crossings, perfect matchings are counted in polynomial time by a determinant-like formula, the Pfaffian, once the edges are suitably signed (Kasteleyn 1967). A graph that has such a signing is called Pfaffian. Every planar graph is Pfaffian, and so are some others.