Dichotomy for Holant Problems of Boolean Domain

22nd Annual ACM-SIAM Symposium on Discrete Algorithms

数学;计算机科学

Jin-Yi Cai ; Pinyan Lu ; Mingji Xia

Others  :  http://www.siam.org/proceedings/soda/2011/SODA11_131_caij.pdf
PID  :  32617

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfac- tion Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant¤(F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these count- ing problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose inner