作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算 • 上一篇    下一篇

Holant问题中的Gadget计算

杨阳   

  1. (复旦大学上海市智能信息处理重点实验室,上海 200433)
  • 收稿日期:2014-12-16 出版日期:2016-01-15 发布日期:2016-01-15
  • 作者简介:杨阳(1989-),男,硕士研究生,主研方向为计算理论。
  • 基金资助:
    国家自然科学基金资助项目(61170208);上海市基础研究基金资助重点项目(12JC1401400)。

Gadget Computation in Holant Problems

YANG Yang   

  1. (Shanghai Key Laboratory of Intelligent Information Processing,Fudan University,Shanghai 200433,China)
  • Received:2014-12-16 Online:2016-01-15 Published:2016-01-15

摘要: 在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

中图分类号: