Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain

A sweeping classification theory for computational counting problems using new techniques and theories.

Jin-Yi Cai (Author), Xi Chen (Author)

9781107062375, Cambridge University Press

Hardback, published 16 November 2017

470 pages
23.6 x 15.8 x 3 cm, 0.77 kg

'There's no doubt in my mind that anyone interested in computational complexity would benefit greatly by reading it. It is a remarkable and indispensable book about a deep and important topic.' Frederic Green, SIGACT News

Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed and gradually increasing the generality and abstraction of the theory. This volume presents the theory on the Boolean domain, and includes a thorough presentation of holographic algorithms, culminating in classifications of computational problems studied in exactly solvable models from statistical mechanics.

1. Counting problems
2. Fibonacci gates and Holant problems
3. Boolean #CSP
4. Matchgates and holographic algorithms
5. 2-spin systems on regular graphs
6. Holant problems and #CSP
7. Holant dichotomy for symmetric constraints
8. Planar #CSP for symmetric constraints
9. Planar Holant for symmetric constraints
10. Dichotomies for asymmetric constraints.

Subject Areas: Computer science [UY], Algorithms & data structures [UMB], Calculus & mathematical analysis [PBK], Number theory [PBH], Mathematical foundations [PBC], Mathematics [PB]