Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

Details Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

2011-08-17

arxiv.org/abs/1108.3383v2

Computer Science

Computational Complexity

26 pages, 14 figures, To appear at ITCS 2012, New version changes: minor copy edits, workaround for arXiv bug that made subscr

Scientific paper

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\}^2 \rightarrow \mathbb{C}$. We show that \[Z(G) = \sum_{\sigma: V(G) \to \{0,1\}} \prod_{(u,v) \in E(G)} f(\sigma(u), \sigma(v)),\] is either computable in polynomial time or #P-hard, depending explicitly on $f$.

Affiliated with

Also associated with

No associations

Rating

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-539669