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

Cassio P. de Campos (Corresponding author), Georgios Stamoulis (Corresponding author), Dennis Weyland

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number104627
Number of pages24
JournalInformation and Computation
Volume275
DOIs
Publication statusPublished - 1 Dec 2020

Funding

The second author's research has been partially supported by the Netherlands Organisation for Scientific Research (NWO) TOP2 ( 617.001.301 ) grant and by the Swiss National Science Foundation as part of the Early Postdoc.Mobility grant P1TIP2_152282 while the author was at the University of Paris-Dauphine. The third author's research has been partially supported by the Swiss National Science Foundation as part of the Early Postdoc.Mobility grant P2TIP2_152293 while the author was at the Department of Economics and Management, University of Brescia, Italy. The authors also thank the reviewers and the editor for very valuable comments and suggestions (including, but not limited to, ideas to prove that can decide the complement of the halting problem and including the discussion regarding the choice of transition amplitudes in a quantum Turing machine) that greatly improved the manuscript.

FundersFunder number
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen ForschungP1TIP2_152282
Nederlandse Organisatie voor Wetenschappelijk Onderzoek617.001.301

    Keywords

    • Computational complexity
    • Probabilistic Turing machines
    • Weighted counting

    Fingerprint

    Dive into the research topics of 'A structured view on weighted counting with relations to counting, quantum computation and applications'. Together they form a unique fingerprint.

    Cite this