Gadgets and anti-gadgets leading to a complexity dichotomy

DOI10.1145/2090236.2090272zbMATH Open1347.68178arXiv1108.3383OpenAlexW2074783224MaRDI QIDQ2826076FDOQ2826076

Authors: Jin-Yi Cai, Michael Kowalczyk, Tyson Williams 

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Abstract: 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}ightarrowmathbbC$. We show that [Z(G) = sum_{sigma: V(G) o {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$.

Full work available at URL: https://arxiv.org/abs/1108.3383

Recommendations

• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Holant problems for 3-regular graphs with complex edge functions
• Holant problems for regular graphs with complex edge functions

zbMATH Keywords

groupspin systemdichotomy theoremholographic algorithmholographic transformationgadget

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• The Well-Calibrated Bayesian
• Title not available (Why is that?)
• The dimensions of individual strings and sequences
• Asymptotic calibration
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Dimension in Complexity Classes
• The reproducible properties of correct forecasts
• Universal prediction
• The Complexity of Forecast Testing

Cited In (9)

• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Facets from gadgets
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• Matchgates revisited

This page was built for publication: Gadgets and anti-gadgets leading to a complexity dichotomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826076)