若干计数问题的复杂性研究
文献类型：学位论文
| 作者 | 夏盟佶 |
| 学位类别 | 博士 |
| 答辩日期 | 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. |
| 公开日期 | 2011-03-17 |
| 源URL | [http://124.16.136.157/handle/311060/6744]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _学位论文 |
| 推荐引用方式 GB/T 7714 | 夏盟佶. 若干计数问题的复杂性研究[D]. 中国科学院软件研究所. 中国科学院研究生院. 2008. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。