Computational complexity of counting and sampling

DOI10.1201/B22024MaRDI QIDQ4685131zbMATH OpenOpenAlexFDO

Authors István Miklós

Publication date 5 October 2018

Full work available at URL https://doi.org/10.1201/b22024

zbMATH Keywords

\#P-complete problemsalgebraic dynamic programmingbioinformaticscomputational complexitycountingholographic algorithmslinear algebraMarkov chainssampling

Mathematics Subject Classification ID

Enumerative combinatorics (05Axx) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) General topics in the theory of algorithms (68W01) Approximation algorithms (68W25) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60) Computational methods for problems pertaining to biology (92-08)

Recommendations

• scientific article; zbMATH DE number 1885142
• scientific article; zbMATH DE number 1566488
• Finite Markov Chains and Algorithmic Applications
• The complexity of counting problems
• Counting constraint satisfaction problems

Cited in

(4)

• A Markov chain on the solution space of edge colorings of bipartite graphs
• Complexity Dichotomies for Counting Problems
• scientific article; zbMATH DE number 850077 (Why is no real title available?)
• Computational Sample Complexity

This page was built for publication: Computational complexity of counting and sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4685131)