Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

We introduce an idea called anti-gadgets for reductions in complexity theory. These anti-gadgets are presented as graph fragments, but their effect is equivalent to erasing the presence of other graph fragments, as if we had managed to include a negative copy of a certain graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z(G) of spin systems over 3-regular directed graphs G, Z(G) = Sigma(sigma: V(G) -> {0, 1}) Pi((u,upsilon) is an element of E(G)) f(sigma(u), sigma(nu)), Where each edge is given a (not necessarily symmetric) complex-valued binary function f : {0, 1}(2) -> C. We show that Z(G) is either computable in polynomial time or #P-hard, depending explicitly on f. When the input graph C is planar, there is an additional class of polynomial time computable partition functions Z(G), while everything else remains #P-hard. Furthermore, this additional class is precisely those that can be transformed by a holographic reduction to matchgates, followed by the Fisher-Kasteleyn-Temperley algoritlun via Pfaffians.