摘要： 在Holant二分理论的证明过程中,F-gate和内插法是常用的归约技术,构件Gadget的计算则是其中的重要步骤。为提高Gadget计算效率,在边枚举和矩阵计算的基础上设计通用算法。针对该算法只能在指数时间内计算的缺点,引入特殊函数给出加速算法,依据自由度优先调用
特殊函数,使Holant问题在多项式计算时间内得到解决。此外,研究发现Gadget计算能够推广为问题Holant(F∪［1,1］),加速算法也同时能描述其相应的易解函数类。
关键词:
计算复杂性,
计数复杂性,
Holant二分理论,
Gadget计算,
内插法,
加速算法
Abstract: F-gate and interpolation method are common reduction techniques in process of Holant dichotomy theorem’s proof,and Gadget computation plays an important role.In order to increase the computational efficiency of Garget,this paper proposes a general algorithm based on edge enumeration and matrix computation.But the general algorithm only computes in exponential time,so aiming at this problem,this paper proposes an accelerative algorithm by introducing the special function.It calls special functions according to the degrees of freedom,which makes Holant problems be solved in polynomial computation time.Moreover,this paper finds that Gadget computation can be extended to Holant(F∪［1,1］) problem,and the accelerated algorithm can also show the tractable families of the problem.
Key words:
computational complexity,
counting complexity,
Holant dichotomy theorem,
Gadget computation,
interpolation method,
accelerated algorithm
中图分类号: