近似计数的算法与复杂性

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.

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

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