中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
题名:
若干计数问题的复杂性研究
作者: 夏盟佶
答辩日期: 2008-06-02
导师: 李昂升
专业: 计算机软件与理论
授予单位: 中国科学院研究生院
授予地点: 中国科学院软件研究所
学位: 博士
关键词: #P完全性 ; #Rtw-CSP ; 全息归约 ; 多项式插值 ; 匹配线路
其他题名: The complexity of some counting problems
部门归属: 计算机科学国家重点实验室
摘要: 本文研究了计算复杂性中的几种归约方法,应用它们刻画了一些计数问题的计算复杂性,或者给出了多项式时间算法,或者证明其是#P完全的;研究了匹配线路和匹配门的性质。 多项式插值(polynomial interpolation)和全息归约(holographic reduction)是两种计数问题间的归约方法。匹配线路(matchcircuit)是一种多项式时间内模拟部分量子线路的方法,匹配门(matchgate)是构成它的零件。以上方法都是Valiant提出的,需要用到矩阵的秩、张量积等代数工具。 本文给出齐次多项式被其在一列递归点列上的值所唯一确定的充分条件,把多项式插值归约推广到高维,使这一方法一般化,用此方法证明了限制到三规则平面偶图的顶点覆盖数目问题仍然是#P完全的,回答了Vadhan提出的问题。 以往的全息归约总是用于平面图完美匹配问题,归根结底是归约到Pfaffian Sum问题,绝大多数全息算法也是解决平面图上的问题。在本文中,全息归约到其它P中问题,给出了两个一般图上的问题的多项式时间算法;首创对#P完全问题做全息归约,同时结合插值归约,在证明计数问题的#P完全性上取得很好的效果,证明了两类问题中一些问题的#P完全性。 构造了一系列EVAL(H)问题(也叫带权重的H染色数目问题),说明了EVAL(H)问题的复杂性和度之间的关系特点。 证明了:对任意k,k比特的匹配门的非退化特征矩阵构成群;2比特的匹配门是通用的。前者推广了蔡进一等的结果,后者回答了Valinat提出的这一未解决问题。使用一些特殊的非退化的简单匹配门,连接到当前的匹配门,以化简其特征矩阵,是证明这两个结果的关键新方法。
英文摘要: We study several reduction methods for computational complexity, and use them to study the computational complexity of counting problems, by proving #P-completeness or giving P-time algorithms. Properties of matchcircuit and matchgate are also studied. Polynomial interpolation and holographic reduction are two important methods for constructing reductions between counting problems. Matchcircuit, which contains matchgates as its components, is a method to simulate some quantum circuits in polynomial time. These three methods, in which algebraic tools such as rank of matrix and tensor products are used, are all proposed by Valiant. We give a sufficient condition which guarantees that the coefficients of a homogeneous polynomial can be uniquely determined by its values on a recurrence sequence. This result enables us to use the polynomial interpolation technique in high dimension and thus generalizes it. Using this generalized polynomial interpolation method, we show that #3-Regular Bipartite Planar Vertex Covers is #P-complete, which answers a question proposed by Vadhan. Holographic reduction is always applied to #Planar-Matchings problem (finally, reduced to Pfaffian Sum problem), and usually gives algorithms for problems on planar graphs. In this thesis, it is applied to some other problems in P, and gives P-time algorithms for two problems on general graphs. What's more, it is applied to #P-hard problems, together with polynomial interpolation technique, proving #P-completeness of quite a few problems. We apply holographic reduction with larger bases, to construct a series of EVAL(H) problems, which show the relationship between complexity of EVAL(H) and the maximum degree of inputs. We also prove that all nonsingular character matrices are closed under matrix inverse operation, so they form a group, and that one bit matchgates and two bits matchgates are universal for matchcircuit. The first result generalizes a result of Cai etc., and the second answers a question proposed by Valiant.
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6744
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200418015029006夏盟佶_paper.pdf(1882KB)----限制开放-- 联系获取全文

Recommended Citation:
夏盟佶. 若干计数问题的复杂性研究[D]. 中国科学院软件研究所. 中国科学院研究生院. 2008-06-02.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[夏盟佶]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[夏盟佶]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace