article

A unifying framework for structural properties of CSPs: definitions, complexity, tractabilit

Authors:

Lucas Bordeaux,

Toni ManciniAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 32, Issue 1

Pages 607 - 629

Published: 01 June 2008 Publication History

Abstract

Literature on Constraint Satisfaction exhibits the definition of several "structural" properties that can be possessed by CSPs, like (in)consistency, substitutability or interchangeability. Current tools for constraint solving typically detect such properties efficiently by means of incomplete yet effective algorithms, and use them to reduce the search space and boost search.

In this paper, we provide a unifying framework encompassing most of the properties known so far, both in CSP and other fields' literature, and shed light on the semantical relationships among them. This gives a unified and comprehensive view of the topic, allows new, unknown, properties to emerge, and clarifies the computational complexity of the various detection problems.

In particular, among the others, two new concepts, fixability and removability emerge, that come out to be the ideal characterisations of values that may be safely assigned or removed from a variable's domain, while preserving problem satisfiability. These two notions subsume a large number of known properties, including inconsistency, substitutability and others.

Because of the computational intractability of all the property-detection problems, by following the CSP approach we then determine a number of relaxations which provide sufficient conditions for their tractability. In particular, we exploit forms of language restrictions and local reasoning.

References

[1]

Bordeaux, L., Cadoli, M., & Mancini, T. (2004). Exploiting fixable, substitutable and determined values in constraint satisfaction problems. In Baader, F., & Voronkov, A. (Eds.), Proceedings of the Eleventh International Conference on Logic for Programming and Automated Reasoning (LPAR 2004), Vol. 3452 of Lecture Notes in Computer Science, pp. 270-284, Montevideo, Uruguay. Springer.

[2]

Bordeaux, L., Cadoli, M., & Mancini, T. (2008). Generalizing consistency and other constraint properties to quantified constraints. ACM Transactions on Computational Logic. To appear.

Digital Library

[3]

Cadoli, M., & Mancini, T. (2007). Using a theorem prover for reasoning on constraint problems. Applied Artificial Intelligence, 21(4/5), 383-404.

Digital Library

[4]

Calabro, C., Impagliazzo, R., Kabanets, V., & Paturi, R. (2003). The complexity of Unique k-SAT: An isolation lemma for k-CNFs. In Proceedings of the Eighteenth IEEE Conference on Computational Complexity (CCC 2003), p. 135 ff., Aarhus, Denmark. IEEE Computer Society Press.

[5]

Chang, C. C., & Keisler, H. J. (1990). Model Theory, 3rd ed. North-Holland.

[6]

Choueiry, B. Y., & Noubir, G. (1998). On the computation of local interchangeability in Discrete Constraint Satisfaction Problems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI'98), pp. 326-333, Madison, WI, USA. AAAI Press/The MIT Press.

Digital Library

[7]

Crawford, J. M. (1992). A theoretical analysis of reasoning by symmetry in first-order logic (extended abstract). In Proceedings of Workshop on Tractable Reasoning, in conjunction with the Tenth National Conference on Artificial Intelligence (AAAI'92), San Jose, CA, USA.

[8]

Crawford, J. M., Ginsberg, M. L., Luks, E. M., & Roy, A. (1996). Symmetry-breaking predicates for search problems. In Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR'96), pp. 148-159, Cambridge, MA, USA. Morgan Kaufmann, Los Altos.

Digital Library

[9]

Davis, M., & Putnam, H. (1960). A computing procedure for Quantification Theory. Journal of the ACM, 7(3), 201-215.

Digital Library

[10]

Dechter, R. (1992). Constraint networks (survey). In Encyclopedia of Artificial Intelligence, 2nd edition, pp. 276-285. John Wiley & Sons.

Digital Library

[11]

Even, S., Selman, A., & Yacobi, Y. (1984). The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2), 159-173.

Digital Library

[12]

Freuder, E. C. (1978). Synthesizing constraint expressions. Communications of the ACM, 21(11), 958-966.

Digital Library

[13]

Freuder, E. C. (1991). Eliminating interchangeable values in Constraint Satisfaction Problems. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI'91), pp. 227-233, Anaheim, CA, USA. AAAI Press/The MIT Press.

[14]

Gent, I. P., & Smith, B. (2000). Symmetry breaking during search in constraint programming. In Proceedings of the Fourteenth European Conference on Artificial Intelligence (ECAI 2000), pp. 599-603, Berlin, Germany.

[15]

Gent, I., Nightingale, P., & Stergiou, K. (2005). QCSP-Solve: A solver for Quantified Constraint Satisfaction Problems. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 138-143, Edinburgh, Scotland. Morgan Kaufmann, Los Altos.

Digital Library

[16]

Giunchiglia, E., Massarotto, A., & Sebastiani, R. (1998). Act, and the rest will follow: Exploiting determinism in planning as satisfiability. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI'98), pp. 948-953, Madison, WI, USA. AAAI Press/The MIT Press.

Digital Library

[17]

Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113.

Digital Library

[18]

Jonsson, P., & Krokhin, A. (2008). Computational complexity of auditing discrete attributes in statistical databases. Journal of Computer and System Sciences. To appear.

Digital Library

[19]

Köbler, J., Schöning, U., & Toráán, J. (1993). The graph isomorphism problem: its computational complexity. Birkhauser Press.

Digital Library

[20]

Lal, A., Choueiry, B., & Freuder, E. C. (2005). Interchangeability and dynamic bundling for non-binary finite CSPs. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI 2005), pp. 397-404, Pittsburgh, PA, USA. AAAI Press/The MIT Press.

Digital Library

[21]

Lenstra, A., & Lenstra, H. W. (1990). Algorithms in number theory. In van Leeuwen, J. (Ed.), The Handbook of Theoretical Computer Science, vol. 1: Algorithms and Complexity . The MIT Press.

Digital Library

[22]

Li, C. M. (2000). Integrating equivalency reasoning into Davis-Putnam procedure. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000), pp. 291-296, Austin, TX, USA. AAAI Press/The MIT Press.

Digital Library

[23]

Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8, 99-118.

Digital Library

[24]

Mancini, T., & Cadoli, M. (2005). Detecting and breaking symmetries by reasoning on problem specifications. In Proceedings of the Sixth International Symposium on Abstraction, Reformulation and Approximation (SARA 2005), Vol. 3607 of Lecture Notes in Artificial Intelligence, pp. 165-181, Airth Castle, Scotland, UK. Springer.

Digital Library

[25]

Mancini, T., & Cadoli, M. (2007). Exploiting functional dependencies in declarative problem specifications. Artificial Intelligence, 171(16-17), 985-1010.

Digital Library

[26]

Mancini, T., Cadoli, M., Micaletto, D., & Patrizi, F. (2008). Evaluating ASP and commercial solvers on the CSPLib. Constraints, 13(4).

Digital Library

[27]

Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999). Determining computational complexity from characteristic phase transitions. Nature, 400, 133-137.

[28]

Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7(2), 85-132.

[29]

Papadimitriou, C. H. (1994). Computational Complexity. Addison Wesley Publishing Company, Reading, Massachussetts, Reading, MA.

[30]

Pyhälä, T. (2004). Factoring benchmarks for SAT solvers. Tech. rep., Helsinki university of technology.

[31]

Safarpour, S., Veneris, A., Drechsler, R., & Lee, J. (2004). Managing don't cares in Boolean Satisfiability. In Proceedings of Design Automation and Test Conference in Europe (DATE 2004), pp. 260-265, Paris, France. IEEE Computer Society Press.

Digital Library

[32]

Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the Tenth ACM Symposium on Theory of Computing (STOC'78), pp. 216-226, San Diego, CA, USA. ACM Press.

Digital Library

[33]

Thiffault, C., Bacchus, F., & Walsh, T. (2004). Solving non-clausal formulas with DPLL search. In Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004), Vol. 3258 of Lecture Notes in Computer Science, pp. 663-678, Toronto, Canada. Springer.

Digital Library

[34]

Valiant, L. G., & Vijay V. Vazirani, V. V. (1986). NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(3), 85-93.

Digital Library

Cited By

Kimura KMakino K(2018)Linear satisfiability preserving assignments (extended abstract)Proceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304812(5622-5626)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304812
Kimura KMakino K(2018)Linear satisfiability preserving assignmentsJournal of Artificial Intelligence Research10.5555/3241691.324169661:1(291-321)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3241691.3241696
Likitvivatanavong CYap R(2013)Eliminating redundancy in CSPs through merging and subsumption of domain valuesACM SIGAPP Applied Computing Review10.1145/2505420.250542213:2(20-29)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2505420.2505422
Show More Cited By

Recommendations

Constraint Hierarchies as Semiring-Based CSPs
ICTAI '09: Proceedings of the 2009 21st IEEE International Conference on Tools with Artificial Intelligence

Constraints provide an effective means for the high-level modeling and reasoning of various problems. In particular, soft constraints are useful since they treat over-constrained problems that naturally arise in real-life applications. Therefore, ...
Semiring-Based CSPs and Valued CSPs: Frameworks, Properties,and Comparison

In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ...
Tractable classes of binary CSPs defined by excluded topological minors
IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence

The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 32, Issue 1

May 2008

974 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 June 2008

Received: 01 January 2008

Published in JAIR Volume 32, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kimura KMakino K(2018)Linear satisfiability preserving assignments (extended abstract)Proceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304812(5622-5626)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304812
Kimura KMakino K(2018)Linear satisfiability preserving assignmentsJournal of Artificial Intelligence Research10.5555/3241691.324169661:1(291-321)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3241691.3241696
Likitvivatanavong CYap R(2013)Eliminating redundancy in CSPs through merging and subsumption of domain valuesACM SIGAPP Applied Computing Review10.1145/2505420.250542213:2(20-29)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2505420.2505422
Likitvivatanavong CYap RShin SMaldonado J(2013)Many-to-many interchangeable sets of values in CSPsProceedings of the 28th Annual ACM Symposium on Applied Computing10.1145/2480362.2480382(86-91)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2480362.2480382
Heinz SSchulz JBeck J(2013)Using dual presolving reductions to reformulate cumulative constraintsConstraints10.1007/s10601-012-9136-918:2(166-201)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1007/s10601-012-9136-9

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents