Descripción del título
Complexity classifications ...
Many fundamental combinatorial problems, arising in such diverse fields as artificial intelligence, logic, graph theory, and linear algebra, can be formulated as Boolean constraint satisfaction problems (CSP). This book is devoted to the study of the complexity of such problems. The authors' goal is to develop a framework for classifying the complexity of Boolean CSP in a uniform way. In doing so, they bring out common themes underlying many concepts and results in both algorithms and complexity theory. The results and techniques presented here show that Boolean CSP provide an excellent framework for discovering and formally validating "global" inferences about the nature of computation
Monografía
monografia Rebiun37054136 https://catalogo.rebiun.org/rebiun/record/Rebiun37054136 m eo d cr bn |||m|||a 101020s2001 pau ob 001 0 eng d 00050988 0-89871-854-6 DT07 siam DT07 SIAM CUNEF 991000509043608131 CaBNVSL. CaBNVSL. CaBNVSL eng 511.3 21 Creignou, Nadia Complexity classifications of Boolean constraint satisfaction problems Nadia Creignou, Sanjeev Khanna, Madhu Sudan Philadelphia, Pa. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104) 2001 Philadelphia, Pa. Philadelphia, Pa. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104) 1 electronic text (xii, 106 p.) digital file 1 electronic text (xii, 106 p.) Text txt computer c online resource cr SIAM monographs on discrete mathematics and applications Bibliographic Level Mode of Issuance: Monograph Includes bibliographical references (p. 97-102) and index Introduction -- Complexity Classes -- Boolean Constraint Satisfaction Problems -- Characterizations of Constraint Functions -- Implementation of Functions and Reductions -- Classification Theorems for Decision, Counting and Quantified Problems -- Classification Theorems for Optimization Problems -- Input-Restricted Constrained Satisfaction Problems -- The Complexity of the Meta-Problems -- Concluding Remarks Many fundamental combinatorial problems, arising in such diverse fields as artificial intelligence, logic, graph theory, and linear algebra, can be formulated as Boolean constraint satisfaction problems (CSP). This book is devoted to the study of the complexity of such problems. The authors' goal is to develop a framework for classifying the complexity of Boolean CSP in a uniform way. In doing so, they bring out common themes underlying many concepts and results in both algorithms and complexity theory. The results and techniques presented here show that Boolean CSP provide an excellent framework for discovering and formally validating "global" inferences about the nature of computation Also available in print version Mode of access: World Wide Web System requirements: Adobe Acrobat Reader English Computational complexity Constraints (Artificial intelligence) Algebra, Boolean Khanna, Sanjeev Sudan, Madhu Society for Industrial and Applied Mathematics 0-89871-479-6 SIAM monographs on discrete mathematics and applications