Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-133 | 23rd January 2017 15:33

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

RSS-Feed




Revision #1
Authors: Georgios Stamoulis, Dennis Weyland, Cassio P. de Campos
Accepted on: 23rd January 2017 15:33
Downloads: 73
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR13-133 | 23rd September 2013 14:11

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


Abstract:

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.



ISSN 1433-8092 | Imprint