Dichotomy for Holant∗ Problems on the Boolean Domain.

Holant problems are a general framework to study counting problems. Both counting constraint satisfaction 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 taking 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 counting problems with the broader scope that allows complex-valued constraint functions, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose dot product with itself is zero. [ABSTRACT FROM AUTHOR]

Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)