期刊
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 80, 期 1, 页码 217-236出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2013.07.003
关键词
CSP; Counting problems; Dichotomy theorem
资金
- NSF [CCF-0830488, CCF-0914969]
- NSFC [61003030]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1217549] Funding Source: National Science Foundation
We prove a complexity dichotomy theorem for the most general form of Boolean #CSP where every constraint function takes values in the field of complex numbers C. We first give a non-trivial tractable class of Boolean #CSP which was inspired by holographic reductions. The tractability crucially depends on algebraic cancelations which are absent for non-negative numbers. We then completely characterize all the tractable Boolean #CSP with complex-valued constraints and show that we have found all the tractable ones, and every remaining problem is #P-hard. We also improve our result by proving the same dichotomy theorem holds for Boolean #CSP with maximum degree 3 (every variable appears at most three times). The concept of Congruity and Semi-congruity provides a key insight and plays a decisive role in both the tractability and hardness proofs. We also introduce local holographic reductions as a technique in hardness proofs. (C) 2013 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据