Nadia Creignou
Abstract
We study the computational complexity of Boolean constraint satisfaction problems with cardinality constraint. A Galois connection between clones and coclones has received a lot of attention in the context of complexity considerations for constraint satisfaction problems. This connection does not seem to help when considering constraint satisfaction problems that support in addition a cardinality constraint. We prove that a similar Galois connection, involving a weaker closure operator and partial polymorphisms, can be applied to such problems. Thus, we establish dichotomies for the decision as well as for the counting problems in Schaefer's framework.
- Allender, E., Bauland, M., Immerman, N., Schnoor, H., and Vollmer, H. 2005. The complexity of satisfiability problems: Refining Schaefer's theorem. In Proceedings of the Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 3618. Springer-Verlag, Berlin, 71--82. Google Scholar
Digital Library
- Bauland, M. and Hemaspaandra, E. 2005. Isomorphic implication. In Proceedings of the Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 3618. Springer-Verlag, Berlin, 119--130. Google ScholarDigital Library
- Bazgan, C. and Karpinski, M. 2005. On the complexity of global constraint satisfaction. In Proceedings of ISAAC'05. Springer-Verlag, Berlin, 624--633. Google ScholarDigital Library
- Bläser, M., Heynen, T., and Manthey, B. 2008. Adding cardinality constraints to integer programs with applications to maximum satisfiability. Inform. Proc. Lett. 105, 194--198. Google ScholarDigital Library
- Bodnarchuk, V. G., Kalužnin, L. A., Kotov, V. N., and Romov, B. A. 1969. Galois theory for Post algebras. I, II. Cybernetics 5, 243--252, 531--539.Google ScholarCross Ref
- Böhler, E., Creignou, N., Reith, S., and Vollmer, H. 2003. Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. ACM-SIGACT Newsl. 34, 4, 38--52.Google ScholarDigital Library
- Böhler, E., Hemaspaandra, E., Reith, S., and Vollmer, H. 2002. Equivalence and isomorphism for Boolean constraint satisfaction. In Proceedings of the 16th International Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol. 2471. Springer Verlag, Berlin, 412--426. Google ScholarDigital Library
- Böhler, E., Hemaspaandra, E., Reith, S., and Vollmer, H. 2004. The complexity of Boolean constraint isomorphism. In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2996. Springer Verlag, Berlin Heidelberg, 164--175.Google Scholar
- Böhler, E., Reith, S., Schnoor, H., and Vollmer, H. 2005. Bases for Boolean co-clones. Inform. Proc. Lett. 96, 59--66. Google ScholarDigital Library
- Creignou, N. 1995. A dichotomy theorem for maximum generalized satisfiability problems. J. Comput. Syst. Sci. 51, 511--522. Google ScholarDigital Library
- Creignou, N. and Hermann, M. 1996. Complexity of generalized satisfiability counting problems. Inform. Comput. 125, 1--12. Google ScholarDigital Library
- Creignou, N., Kolaitis, P., and Zanuttini, B. 2008. Structure identification for Boolean relations and plain bases for co-clones. J. Comput. Syst. Sci. 74, 1103--1115. Google ScholarDigital Library
- Creignou, N. and Vollmer, H. 2008. Boolean constraint satisfaction problems: when does Post's lattice help? In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer, Eds. Vol. 5250. Springer Verlag, Berlin, 3--37. Google ScholarDigital Library
- Creignou, N. and Zanuttini, B. 2006. A complete classification of the complexity of propositional abduction. SIAM J. Comput. 36, 1, 207--229. Google ScholarDigital Library
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York. Google ScholarDigital Library
- Geiger, D. 1968. Closed systems of functions and predicates. Pac. J. Math 27, 1, 95--100.Google ScholarCross Ref
- Jeavons, P. G. 1998. On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200, 185--204. Google ScholarDigital Library
- Khanna, S., Sudan, M., Trevisan, L., and Williamson, D. 2001. The approximability of constraint satisfaction problems. SIAM J. Comput. 30, 1863--1920. Google ScholarDigital Library
- Kirousis, L. M. and Kolaitis, P. G. 2003. The complexity of minimal satisfiability problems. Inform. Comput. 187, 1, 20--39. Google ScholarDigital Library
- Marx, D. 2005. Parameterized complexity of constraint satisfaction problems. Computati. Complex. 14, 2, 153--183. Google ScholarDigital Library
- Post, E. L. 1941. The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5, 1--122.Google Scholar
- Reith, S. and Vollmer, H. 2003. Optimal satisfiability for propositional calculi and constraint satisfaction problems. Inform. Comput. 186, 1, 1--19. Google ScholarDigital Library
- Romov, B. A. 1981. The algebras of partial functions and their invariants. Cybernet. Syst. Anal. 17, 2, 157--167.Google ScholarCross Ref
- Schaefer, T. J. 1978. The complexity of satisfiability problems. In Proccedings of the 10th Symposium on Theory of Computing. ACM, New York, 216--226. Google ScholarDigital Library
- Schnoor, H. and Schnoor, I. 2008. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer, Eds. Vol. 5250. Springer Verlag, Berlin, 229--254. Google ScholarDigital Library
- Sviridenko, M. I. 2001. Best possible approximation algorithm for MAX-SAT with cardinality constraint. Algorithmica 30, 3, 398--405.Google ScholarCross Ref
- Toda, S. and Watanabe, O. 1992. Polynomial time 1-Turing reductions from #PH to #P. Theoret. Comput. Sci. 100, 205--221. Google ScholarDigital Library
- Zankó, V. 1991. #P-completeness via many-one reductions. Int. J. Found. Comput. Sci. 2, 77--82.Google ScholarCross Ref
Index Terms
- Nonuniform Boolean constraint satisfaction problems with cardinality constraint
Recommendations
Hard constraint satisfaction problems have hard gaps at location 1
An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
Tropically Convex Constraint Satisfaction
A semilinear relation S⊆źn$S \subseteq {\mathbb {Q}}^{n}$ is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in ...
The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logical sentence consisting of a ...
Reviews
Vladik Ya. Kreinovich
In a Boolean constraint satisfaction problem CSP( S ), we fix a finite set S of Boolean relations. Given a formula F -a conjunction of applications of some relations from S to variables-we must check whether F is satisfiable. For S = { a \/ b \/ c }, we get 3-conjunctive normal form (CNF) formulas for which satisfiability is nondeterminstic polynomial-time (NP) complete; for S = { a \/ b }, we get 2-CNF formulas for which satisfiability is in P. It is known that for every set S , CSP( S ) is either NP-complete or in P. The paper extends this result to problems Bal-CSP( S ) and k -ones( S ), in which we are interested only in satisfying vectors that have either exactly as many ones as zeros (for Bal-CSP( S )) or exactly k ones (for k -ones( S )), for a given k . For both classes, we have the same NP-complete-P dichotomy, and the problem is in P only when each relation from S is either unary or is a binary exclusive-or applied to two literals. For similar counting problems, where we are interested in the number of solutions, we get a similar dichotomy: #P-complete or in P, with the same cases of P. The proof is based on a new Galois correspondence between Boolean functions and Boolean relations: to every set of relations, we associate all partial functions that preserve all these relations, and to every set of partial functions, we associate the set of all relations that are preserved under these functions. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments