Planar Perfect Matching Counting is as Hard as Determinants

Radu Curticapean, Jiaheng Wang

In the 1960s, Fisher, Kasteleyn and Temperley designed an ingenious algorithm for computing the partition function of the dimer model, or equivalently, for counting perfect matchin…