Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path of polynomial-time non-deterministic Turing machines and the goal is to compute the sum of the weights of all paths (instead of just computing the number of accepting paths). Useful closure properties and plenty of applications make weighted counting problems interesting. The general definition of these problems captures even undecidable problems, but it turns out that obtaining an exponentially small additive approximation is just as hard as solving conventional counting problems. In many cases such an approximation is sufficient and working with weighted counting problems tends to be very convenient. We present a structured view on weighted counting by defining classes that depend on the range of the function that assigns weights to paths and by showing the relationships between these different classes. These classes constitute generalizations of the usual counting problems. Weighted counting allows us to easily cast a number of famous results of computational complexity in its terms, especially regarding counting and quantum computation. Moreover, these classes are flexible enough and capture the complexity of various problems in fields such as probabilistic graphical models and stochastic combinatorial optimization. Using the weighted counting terminology and our results, we are able to simplify and answer some open questions in those fields.
翻译:加权计数问题是计算问题的自然概括化,在计算问题的每个计算路径中,一个重量与多米时间的非决定性图灵机器的每个计算路径都有关联,目标是计算所有路径的加权和总和(而不是仅仅计算接受路径的数目)。有用的封闭属性和大量应用使加权计数问题变得有趣。这些问题的一般定义甚至可以捕捉无法量化的问题,但事实证明,获得一个指数性的小添加近似接近与解决常规计数问题一样困难。在许多情况下,这种近似足够,而且处理加权计数问题往往非常方便。我们提出一个结构化的加权计数观点,方法是根据给路径分配加权的功能范围来确定加权计数,并显示这些不同分类之间的关系。这些分类是通常计数问题的概括性。 加权计算让我们很容易地在计算方法上得出一些著名的计算复杂性结果,特别是在计数和量计算方面。此外,这些分类足够灵活,并捕捉到一些领域的各种问题的复杂性,例如,例如,比较性图形模型和可变化的调术语,这些是我们用来进行加权的计算。