A Structured View on Weighted Counting with Relations to Counting, Quantum Computation and Applications

Understand

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.