Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
[go: Go Back, main page]






                                      Complexity Classifications of Boolean Constraint Satisfaction Problems

                                                            Nadia Creignou, Sanjeev Khanna, and Madhu Sudan

                                             SIAM Monographs on Discrete Mathematics and Applications.


Boolean constraint satisfaction problems have been studied from the point of view of decidability, optimization, counting, among others, and a variety of theorems classifying their complexity have been obtained. However, almost every such effort developed its own set of specific tools to obtain the results, thus obscuring many fundamental connections between these results and techniques. The aim of this monograph is to give a unified treatise of complexity classification results for boolean constraint satisfaction problems, and to develop a framework for proving all these results in a uniform way. Our work covers most of the previously known results and presents many new ones, demonstrating the effectiveness of our framework. Together, these results shed some light on ``what renders some problems easy and others hard" in various complexity classes.