We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z(G) on 3-regular directed graphs G, where each edge is given a complex-valued binary function f: {0,1}² → C. We show that

[EQUATION]

is either computable in polynomial time or #P-hard, depending explicitly on f.

To state the dichotomy theorem more explicitly, we show that the partition function Z(G) on 3-regular directed graphs G is computable in polynomial time when f belongs to one of four classes, which can be described as (1) degenerate, (2) generalized disequality, (3) generalized equality, and (4) affine after a holographic transformation. In all other cases it is #P-hard. Here class (4), after a holographic transformation, can also be described as an exponential quadratic polynomial of the form i^Q(x, y), where i = √-1 and the cross term xy in the quadratic polynomial Q(x, y) has an even coefficient. If the input graph G is planar, then an additional class of functions becomes computable in polynomial time, and everything else remains #P-hard. This additional class is precisely those which can be computed by holographic algorithms with matchgates, making use of the Fisher-Kasteleyn-Temperley algorithm via Pfaffians.

There is a long history in the study of "Exactly Solved Models" in statistical physics. In the language of complexity theory, physicists' notion of an "Exactly Solvable" system corresponds to a system with a polynomial time computable partition function. A central question is to identify which "systems" can be solved "exactly" and which "systems" are "difficult". While in physics, there is no rigorous definition of being "difficult", complexity theory supplies the proper notion---#P-hardness.

The main innovation in this paper is the idea of an anti-gadget. It is analogous to the pairing of a particle and its anti-particle in physics. Coupled with the idea of anti-gadgets, we also introduce a general way of proving #P-hardness by two types of gadgets called recursive gadgets and projector gadgets. We prove a Group Lemma which spells out a general condition for the technique to succeed. This Group Lemma states that as long as the group generated by the transition matrices of the constructed gadgets is infinite, then one can interpolate all unary functions---a key step in the proof of #P-hardness. Interpolation is carried out by forming a Vandermonde system and proving that it is of full rank. The anti-gadget concept makes the transition to group theory very natural and seamless.

Not only is the idea of anti-gadgets useful in proving a new complexity dichotomy theorem in counting complexity, we also show that anti-gadgets provide a simple explanation for some miraculous cancellations that were observed in previous results. Furthermore, anti-gadgets can also guide the search for gadget sets more by design than by chance.