🎉   Please check out our new website over at books-etc.com.

Seller
Your price
£118.91
RRP: £126.00
Save £7.09 (6%)
Dispatched within 3-4 working days.

Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain

By (author) Jin-Yi Cai, Xi Chen
Format: Hardback
Publisher: Cambridge University Press, Cambridge, United Kingdom
Published: 16th Nov 2017
Dimensions: w 158mm h 236mm d 30mm
Weight: 770g
ISBN-10: 1107062373
ISBN-13: 9781107062375
Barcode No: 9781107062375
Trade or Institutional customer? Contact us about large order quotes.
Synopsis
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.

New & Used

Seller Information Condition Price
-New£118.91
+ FREE UK P & P

What Reviewers Are Saying

Submit your review
Newspapers & Magazines
'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