TY - JOUR

T1 - A structured view on weighted counting with relations to counting, quantum computation and applications

AU - de Campos, Cassio P.

AU - Stamoulis, Georgios

AU - Weyland, Dennis

PY - 2020/12/1

Y1 - 2020/12/1

N2 - 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. The goal is to compute the sum of weights of all paths (instead of number of accepting paths). Useful properties and plenty of applications make them interesting. The definition captures even undecidable problems, but obtaining an exponentially small additive approximation is just as hard as solving conventional counting. We present a structured view by defining classes that depend on the functions that assign weights to paths and by showing their relationships and how they generalize counting problems. Weighted counting is flexible and allows us to cast a number of famous results of computational complexity, including quantum computation, probabilistic graphical models and stochastic combinatorial optimization. Using the weighted counting terminology, we are able to simplify and to answer some open questions.

AB - 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. The goal is to compute the sum of weights of all paths (instead of number of accepting paths). Useful properties and plenty of applications make them interesting. The definition captures even undecidable problems, but obtaining an exponentially small additive approximation is just as hard as solving conventional counting. We present a structured view by defining classes that depend on the functions that assign weights to paths and by showing their relationships and how they generalize counting problems. Weighted counting is flexible and allows us to cast a number of famous results of computational complexity, including quantum computation, probabilistic graphical models and stochastic combinatorial optimization. Using the weighted counting terminology, we are able to simplify and to answer some open questions.

KW - Computational complexity

KW - Probabilistic Turing machines

KW - Weighted counting

UR - http://www.scopus.com/inward/record.url?scp=85090163558&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104627

DO - 10.1016/j.ic.2020.104627

M3 - Article

AN - SCOPUS:85090163558

VL - 275

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104627

ER -