Journal
ACM TRANSACTIONS ON COMPUTATION THEORY
Volume 11, Issue 2, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3305272
Keywords
Holant problem; partition function; dichotomy theorem; holographic algorithms; interpolation; counting complexity
Categories
Funding
- NSF [CCF-1217549, CCF-1714275]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available