Holographic algorithms beyond matchgates
Holographic algorithms beyond matchgates
复制标题
超越匹配门的全息算法
DOI：
10.1016/j.ic.2018.01.002
复制
发表时间：
2018
影响因子：
1
通讯作者：
Williams, Tyson
中科院分区：
文献类型：
--
作者：
Cai, Jin-Yi;Guo, Heng;Williams, Tyson
Valiant 引入的全息算法有两个组成部分：匹配门（matchgates），它是通过加权平面完美匹配实现局部约束函数的小工具；全息约简（holographyreductions），它通过基础变换显示不同描述的问题之间的等价性。在本文中，我们用仿射类型和乘积类型约束函数替换上述范例中的匹配门，这些函数在一般（不一定是平面）图中很容易处理。我们提出多项式时间算法来确定给定的计数问题是否具有由仿射或乘积类型函数定义的另一个问题的全息还原。我们还针对对称函数的相同问题给出了多项式时间算法，其中复杂性是根据（指数级更多）简洁表示来衡量的。后一个结果意味着对称布尔 Holant 二分法（Cai、Guo 和 Williams，SICOMP 2016）是有效可判定的。我们的证明技术主要是代数的。
Holographic algorithms introduced by Valiant have two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via basis transformations. In this paper, we replace matchgates in the paradigm above by theaffinetype and theproducttype constraint functions, which are known to be tractable in general (not necessarily planar) graphs. We present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. We also give polynomial-time algorithms to the same problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The latter result implies that the symmetric Boolean Holant dichotomy (Cai, Guo, and Williams, SICOMP 2016) is efficiently decidable. Our proof techniques are mainly algebraic.