10. Concluding Remarks
Society for Industrial and Applied Mathematics eBooks · 2001
We have presented a taxonomy of the computational complexity of problems derived from Boolean constraint satisfaction. In the process we have seen some of the central complexity classes such as NP, NC, PSPACE, #P and NPO. When specialized to Boolean constraint satisfaction, these classes partition nicely into just finitely many equivalence classes — where problems within an equivalence class are reducible to one another. A central idea in establishing these partitions is the notion of implementations. Implementations allowed us to build in a unified manner a variety of different reductions addressing the varying goals of the decision, counting and optimization problems. The basic toolkit turns out to be significantly more compact than the wide variety of purposes that it is used for. One of the most significant conclusions we draw from the study of constraint satisfaction problems is that it provides an excellent platform to search for a “formal basis” for “empirical observations”. Complexity theory is intended to study the most general forms of computations. However, the generality often poses a barrier when one tries to formalize a noticeable trend among natural problems. Typically, the moment one tries to formalize the trend, a counterexample is found. Usually the counterexample is unnatural, but there is no way to formalize the notion of naturality either! In contrast, specializing classes such as NP, PSPACEand NPO to Boolean constraint satisfaction creates “miniaturized imprints” of these classes that are refined enough to exhibit many phenomena observed in the parent classes and yet coarse enough to preserve such phenomena over all problems contained in them. Consider for example the unifying notion of reductions used for NP-completeness. Most known reductions are based on “gadgets” — an informal theme that signifies that a combinatorial construct has been used to convert one problem to another. Much of the work towards formally studying gadgets has been confined to specific instances of source and target problems of the reduction (see, for instance, [7]). The finite nature of such problem-specific explorations inherently lacks the ability to highlight any general results that describe the ubiquitous nature of gadget reductions. However, when restricted to constraint satisfaction problems, the elusive notion of a “gadget” reduction can be formalized — it is indeed the notion of reduction via implementations. The results described in the earlier chapters give a very satisfactory explanation of the seemingly universal nature of these reductions. Constraint satisfaction problems play a particularly significant role in the study of optimization problems. The current decade (1990–2000) has seen an explosion of research studying the approximability of optimization problems.