Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
A comprehensive guide to counting problems in complexity theory
Jin-Yi Cai author Xi Chen author
Format:Hardback
Publisher:Cambridge University Press
Published:16th Nov '17
Currently unavailable, and unfortunately no date known when it will be back
This book explores complexity theory, focusing on counting problems in the Boolean domain, providing classifications and techniques for researchers and students.
In Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain, the authors delve into the intricacies of complexity theory, aiming to classify computational problems based on their inherent complexities. This book introduces innovative techniques that enhance the understanding of counting problems specifically within the Boolean domain. The content is designed to be accessible to both researchers and graduate students, making it a valuable resource for those new to the field as well as seasoned professionals.
The authors focus on providing dichotomy classifications for various counting problems, particularly in the context of decision problems categorized under P and NP. They explore a range of computational challenges, including partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. By gradually building up the necessary proof techniques, the book ensures that readers develop a solid foundation in computational complexity theory while navigating through increasingly abstract concepts.
Additionally, Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain presents a comprehensive examination of holographic algorithms. This culminates in detailed classifications of computational problems that are pertinent to exactly solvable models in statistical mechanics. The book's structured approach not only clarifies complex ideas but also fosters a deeper understanding of the subject, making it an essential addition to the literature on computational complexity.
'This remarkable volume presents persuasive evidence that computer applications obey beautiful unities: within the significant classes considered, the problems that are not known to be polynomial time computable are all reducible to each other by a small number of elegant techniques. The treatment is original, comprehensive and thought provoking.' Leslie Valiant, Harvard University, Massachusetts
'This book provides a thorough study of the complexity of counting. These basic problems arise in statistical physics, optimization, algebraic combinatorics and computational complexity. The past fifteen years of research have led to a (surprisingly clean) complete characterization of their complexity in the form of a 'dichotomy theorem', whose proof is the main goal of this volume. Along the way, the authors provide detailed explanations of basic methods for studying such problems, including holographic algorithms and reductions. The book is very well written and organized, and should be useful to researchers and graduate students in the fields above.' Avi Wigderson, Institute for Advanced Study, Princeton, New Jersey
'This book would make an excellent introduction to the field of counting complexity for a mathematically literate reader with little or no background in computational complexity … Many of the results included in the book are recent, and have not appeared in book form before. As such, this thorough, self-contained treatment of the subject makes a very valuable contribution to the literature.' Kitty Meeks, MathSciNet
'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
ISBN: 9781107062375
Dimensions: 236mm x 158mm x 30mm
Weight: 770g
470 pages