Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain - Tapa dura

Cai, Jin-Yi; Chen, Xi

 
9781107062375: Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
Tapa dura
ISBN 10: 1107062373 ISBN 13: 9781107062375
Editorial: Cambridge University Press, 2017

Sinopsis

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.

"Sinopsis" puede pertenecer a otra edición de este libro.

Acerca de los autores

Jin-Yi Cai is Professor of Computer Science and the Steenbock Professor of Mathematical Sciences at the University of Wisconsin, Madison. He studied at Fudan University, Shanghai (class of 77) and at Cornell University, New York, receiving his Ph.D. in 1986. He held faculty positions at Yale University, Connecticut (1986–1989), Princeton University, New Jersey (1989–1993), and State University of New York, Buffalo (1993–2000), where he rose from Assistant Professor to Full Professor in 1996. He received a Presidential Young Investigator Award (1990), an Alfred P. Sloan Fellowship (1994), and a John Simon Guggenheim Fellowship (1998). He is a Fellow of the Association for Computing Machinery (ACM) and the American Association for the Advancement of Science (AAAS).

Xi Chen is Associate Professor of Computer Science at Columbia University, New York. He studied at Tsinghua University and received his Ph.D. in 2007. His research focuses on complexity theory and algorithmic game theory. He is the recipient of a NSF CAREER Award, an Alfred P. Sloan Fellowship (2012), and an European Association for Theoretical Computer Science (EATCS) Presburger Award (2015).

"Sobre este título" puede pertenecer a otra edición de este libro.

Editorial
Cambridge University Press
Año de publicación
2017
Idioma
Inglés
ISBN 10 
1107062373
ISBN 13 
9781107062375
Encuadernación
Tapa dura
Número de páginas
470
Contacto del fabricante
no disponible
Persona responsable
Avery
https://www.avery.fr/

chemin des peupliers 27
Dardilly
Francia