论文标题
真正的布尔人问题的二分法
A Dichotomy for Real Boolean Holant Problems
论文作者
论文摘要
我们证明了带有随意的约束功能集的布尔域上的Holant问题的复杂性二分法。这些约束函数不必对称，也不像以前的结果那样假设任何辅助功能。事实证明，对实值约束功能的每一集$ \ MATHCAL {f} $，Holant $（\ Mathcal {f}）$是P imple可计算或＃p-hard。分类具有明确的标准。这是对这个问题的大量研究的高潮，它使用了许多研究人员的先前结果和技术。一些特别有趣的混凝土功能$ f_6 $，$ f_8 $及其相关家庭在量子信息理论中与贝尔状态相关的非凡封闭属性在此证明中起着重要作用。
We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions as in previous results. It is proved that for every set $\mathcal{F}$ of real-valued constraint functions, Holant$(\mathcal{F})$ is either P-time computable or #P-hard. The classification has an explicit criterion. This is the culmination of much research on this problem, and it uses previous results and techniques from many researchers. Some particularly intriguing concrete functions $f_6$, $f_8$ and their associated families with extraordinary closure properties related to Bell states in quantum information theory play an important role in this proof.
