ECCC-Report TR13-133https://eccc.weizmann.ac.il/report/2013/133Comments and Revisions published for TR13-133en-usThu, 10 Jan 2019 15:29:17 +0200
Revision 2
| A Structured View on Weighted Counting with Relations to Quantum Computation and Applications |
Cassio P. de Campos,
Georgios Stamoulis,
Dennis Weyland
https://eccc.weizmann.ac.il/report/2013/133#revision2Weighted 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.Thu, 10 Jan 2019 15:29:17 +0200https://eccc.weizmann.ac.il/report/2013/133#revision2
Revision 1
| A Structured View on Weighted Counting with Relations to Quantum Computation and Applications |
Georgios Stamoulis,
Dennis Weyland,
Cassio P. de Campos
https://eccc.weizmann.ac.il/report/2013/133#revision1Weighted 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.Mon, 23 Jan 2017 15:33:51 +0200https://eccc.weizmann.ac.il/report/2013/133#revision1
Paper TR13-133
| A Structured View on Weighted Counting with Relations to Quantum Computation and Applications |
Cassio P. de Campos,
Georgios Stamoulis,
Dennis Weyland
https://eccc.weizmann.ac.il/report/2013/133Weighted 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.Mon, 23 Sep 2013 14:31:07 +0300https://eccc.weizmann.ac.il/report/2013/133