Holant问题中的Gadget计算

• 作者: 杨阳
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 计算复杂性 计数复杂性 Holant二分理论 Gadget计算 内插法 加速算法
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 先进计算
• 页码范围: 7-10
• 页数: 4页
• 分类号: TP301
• 字数: 3477字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2016.01.002

摘要

在Holant二分理论的证明过程中,F-gate和内插法是常用的归约技术,构件Gadget的计算则是其中的重要步骤.为提高Gadget计算效率,在边枚举和矩阵计算的基础上设计通用算法.针对该算法只能在指数时间内计算的缺点,引入特殊函数给出加速算法,依据自由度优先调用特殊函数,使Holant问题在多项式计算时间内得到解决.此外,研究发现Gadget计算能够推广为问题Holant(F∪[1,1]),加速算法也同时能描述其相应的易解函数类.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨阳	复旦大学上海市智能信息处理重点实验室	9	98	4.0	9.0