Abstract
We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complexvalued symmetric constraint functions F on Boolean variables. This extends and unites all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a nite modulus). We define and characterize all symmetric vanishing signatures. They turned out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion expressible in terms of holographic transformations. A Holant problem defined by a set of constraint functions F is solvable in polynomial time if it satisfies this tractability criterion, and is #Phard otherwise. The tractability criterion can be intuitively stated as follows: A set F is tractable if (1) every function in F has arity at most two, or (2) F is transformable to an affine type, or (3) F is transformable to a product type, or (4) F is vanishing, combined with the right type of binary functions, or (5) F belongs to a special category of vanishing type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean #CSP. Holographic transformations play an indispensable role as both a proof technique and in the statement of the tractability criterion.
Original language  English 

Pages (fromto)  16711728 
Number of pages  57 
Journal  SIAM Journal on Computing 
Volume  45 
Issue number  5 
DOIs  
Publication status  Published  1 Sep 2016 
Fingerprint Dive into the research topics of 'A Complete Dichotomy Rises from the Capture of Vanishing Signatures'. Together they form a unique fingerprint.
Profiles

Heng Guo
 School of Informatics  Lecturer in Algorithms and Complexity
 Laboratory for Foundations of Computer Science  Lecturer in Algorithms and Complexity
 Foundations of Computation
Person: Academic: Research Active (Teaching)