Progress in complexity of counting problems

DOI10.1007/978-3-642-21204-8_1MaRDI QIDQ3004647zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai

Publication date 3 June 2011

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Complexity dichotomy for counting problems
• Complexity dichotomies of counting problems
• Holant problems and counting CSP
• The complexity of partition functions
• Automata, Languages and Programming

Cites work

• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• Holant problems and counting CSP
• Holographic Algorithms
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms: from art to science
• On the complexity of \#CSP
• Operations with structures
• The complexity of satisfiability problems
• The Complexity of the Counting Constraint Satisfaction Problem

Cited in

(3)

• Complexity dichotomies of counting problems
• scientific article; zbMATH DE number 850077 (Why is no real title available?)
• Complexity dichotomy for counting problems

This page was built for publication: Progress in complexity of counting problems

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