Complexity dichotomy for counting problems

DOI10.1007/978-3-642-37064-9_1MaRDI QIDQ4910437zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai

Publication date 18 March 2013

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-37064-9_1

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Progress in complexity of counting problems
• Complexity dichotomies of counting problems
• Holant problems and counting CSP
• Computational complexity of Holant problems
• The complexity of partition functions

Cited in

(7)

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Complexity dichotomies of counting problems
• Counting Value Sets: Algorithm and Complexity
• Progress in complexity of counting problems
• The Parameterized Complexity of Counting Problems
• scientific article; zbMATH DE number 850077 (Why is no real title available?)
• scientific article; zbMATH DE number 7075922 (Why is no real title available?)

This page was built for publication: Complexity dichotomy for counting problems

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