Limit search to available items
Book Cover
E-book
Author Cai, Jin-yi, 1961- author.

Title Complexity dichotomies for counting problems. Volume 1, Boolean domain / Jin-Yi Cai, Xi Chen
Published Cambridge, United Kingdom : Cambridge University Press, 2017

Copies

Description 1 online resource : illustrations
Contents Volume 1. Boolean domain
Summary 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
Bibliography Includes bibliographical references and index
Notes Vendor-supplied metadata
Subject Algebra, Boolean.
Computational complexity.
Combinatorial enumeration problems.
Homomorphisms (Mathematics)
MATHEMATICS -- General.
Complejidad computacional
Algebra, Boolean
Combinatorial enumeration problems
Computational complexity
Homomorphisms (Mathematics)
Form Electronic book
Author Chen, Xi (Computer science professor), author.
ISBN 9781108523721
1108523722
9781108505840
1108505848
9781107062375
1107062373
9781107477063
1107477069
1107635608
9781107635609
Other Titles Boolean domain