Revision #2 Authors: Georgios Stamoulis, Dennis Weyland, Cassio P. de Campos

Accepted on: 10th January 2019 15:29

Downloads: 243

Keywords:

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by defining several 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 strict generalizations of the usual counting problems. Weighted counting allows us to easily cast a number of famous complexity theoretic results in its terms, especially for quantum computation. Moreover, these classes are flexible enough and capture the complexity of various problems in fields such as probabilistic networks and stochastic combinatorial optimization. Using the weighted counting terminology and our results, we are able to greatly simplify and answer some long-standing open questions in those fields.

Revision #1 Authors: Georgios Stamoulis, Dennis Weyland, Cassio P. de Campos

Accepted on: 23rd January 2017 15:33

Downloads: 391

Keywords:

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by defining several 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 strict generalizations of the usual counting problems. Weighted counting allows us to easily cast a number of famous complexity theoretic results in its terms, especially for quantum computation. Moreover, these classes are flexible enough and capture the complexity of various problems in fields such as probabilistic networks and stochastic combinatorial optimization. Using the weighted counting terminology and our results, we are able to greatly simplify and answer some long-standing open questions in those fields.

Changed the definition of "equivalence". Many details added and proofs have been expanded. There is a more detailed discussion on the implications of the framework.

TR13-133 Authors: Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland

Publication: 23rd September 2013 14:31

Downloads: 2277

Keywords:

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by defining several 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 strict generalizations of the usual counting problems. Weighted counting allows us to easily cast a number of famous complexity theoretic results in its terms, especially for quantum computation. Moreover, these classes are flexible enough and capture the complexity of various problems in fields such as probabilistic networks and stochastic combinatorial optimization. Using the weighted counting terminology and our results, we are able to greatly simplify and answer some long-standing open questions in those fields.