近似计数的算法与复杂性

项目名称： 近似计数的算法与复杂性

项目编号： No.61272081

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 尹一通

作者单位： 南京大学

项目金额： 80万元

中文摘要： 计数问题是一类很根本的计算问题，在计算机科学的许多分支都有重要的应用。然而几乎所有非平凡的计数问题精确求解都是极其困难的，另一方面许多计数问题都有性能优越的近似算法。因此近似计数实际上代表了计数问题是否在现实意义下可解。本项目将系统的研究近似计数的算法和复杂性。对于抽象的数学框架所描述的一大类计数问题，设计近似计数算法，证明近似计数复杂性，即不可近似性。通过这种方式来探索近似计数的能力和界限。

中文关键词： 计数问题；近似算法；复杂性；不可近似性；相变

英文摘要： Counting problems are a fundamental class of computation problems, which have important applications in many areas of Computer Science. However, for almost all non-trivial counting problems, it is extremely hard to compute the exact solution. On the other hand, many counting problems have efficient approximation algorithms, thus approximate counting actually represents whether a given counting problem is solvable in practice. This project will systematically study the algorithms and complexity of approximate counting. We will design approximate counting algorithms or prove inapproximability for classes of counting problems described by abstract frameworks. By doing so we can explore the power and limitation of approximate counting.

英文关键词： counting problem；approximation algorithms；complexity；inapproximability；phase transition