On minimal constraint networks. (English) Zbl 1270.68268
Summary: In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be NP-hard. We prove this conjecture. We also prove a conjecture by Dechter and Pearl stating that for \(k\geq 2\) it is NP-hard to decide whether a single constraint can be decomposed into an equivalent \(k\)-ary constraint network. We show that this holds even in case of bi-valued constraints where \(k\geq 3\), which proves another conjecture of Dechter and Pearl. Finally, we establish the tractability frontier for this problem with respect to the domain cardinality and the parameter \(k\).
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68P15 | Database theory |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Samson Abramsky, Relational databases and Bellʼs theorem, submitted for publication.; Samson Abramsky, Relational databases and Bellʼs theorem, submitted for publication. · Zbl 1278.81101 |
| [2] | Samson Abramsky, Relational hidden variables and non-locality, Studia Logica, in press.; Samson Abramsky, Relational hidden variables and non-locality, Studia Logica, in press. · Zbl 1278.81101 |
| [3] | Adler, Isolde; Gottlob, Georg; Grohe, Martin, Hypertree width and related hypergraph invariants, European J. Combin., 28, 8, 2167-2181 (2007) · Zbl 1127.05065 |
| [4] | Bessiere, Christian, Constraint propagation, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming, Chapter 3 (2006)) · Zbl 1142.68007 |
| [5] | Cadoli, Marco; Donini, Francesco M., A survey on knowledge compilation, AI Commun., 10, 3-4, 137-150 (1997) |
| [6] | Hervé Cros, Compréhension et apprentissage dans les résaux de contraintes, PhD thesis, Université de Montpellier, 2003, cited in [4]; Hervé Cros, Compréhension et apprentissage dans les résaux de contraintes, PhD thesis, Université de Montpellier, 2003, cited in [4] |
| [7] | Dechter, Rina, From local to global consistency, Artificial Intelligence, 55, 1, 87-108 (1992) · Zbl 0762.68053 |
| [8] | Dechter, Rina, Constraint Processing (2003), Morgan Kaufmann · Zbl 1057.68114 |
| [9] | Dechter, Rina; Pearl, Judea, Structure identification in relational data, Artificial Intelligence, 58, 237-270 (1992) · Zbl 0782.68095 |
| [10] | Fleischanderl, Gerhard; Friedrich, Gerhard; Haselböck, Alois; Schreiner, Herwig; Stumptner, Markus, Configuring large systems using generative constraint satisfaction, IEEE Intell. Syst., 13, 4, 59-68 (1998) |
| [11] | Daya Ram Gaur, Algorithmic complexity of some constraint satisfaction problems, Master of Science (MSc) Thesis, Simon Fraser University, April 1995, currently available at http://summit.sfu.ca/system/files/iritems1/6666/b17427204.pdf; Daya Ram Gaur, Algorithmic complexity of some constraint satisfaction problems, Master of Science (MSc) Thesis, Simon Fraser University, April 1995, currently available at http://summit.sfu.ca/system/files/iritems1/6666/b17427204.pdf |
| [12] | Gebser, Martin; Kaufmann, Benjamin; Neumann, André; Schaub, Torsten, Conflict-driven answer set enumeration, (Baral, Chitta; Brewka, Gerhard; Schlipf, John S., LPNMR. LPNMR, Lecture Notes in Comput. Sci., vol. 4483 (2007), Springer), 136-148 · Zbl 1149.68332 |
| [13] | Gebser, Martin; Kaufmann, Benjamin; Schaub, Torsten, Solution enumeration for projected boolean search problems, (van Hoeve, Willem Jan; Hooker, John N., CPAIOR. CPAIOR, Lecture Notes in Comput. Sci., vol. 5547 (2009), Springer), 71-86 · Zbl 1241.68100 |
| [14] | Gottlob, Georg; Leone, Nicola; Scarcello, Francesco, A comparison of structural CSP decomposition methods, Artificial Intelligence, 124, 2, 243-282 (2000) · Zbl 0952.68044 |
| [15] | Gottlob, Georg; Leone, Nicola; Scarcello, Francesco, Hypertree decompositions: A survey, (Sgall, Jiri; Pultr, Ales; Kolman, Petr, MFCS. MFCS, Lecture Notes in Comput. Sci., vol. 2136 (2001), Springer), 37-57 · Zbl 1001.05087 |
| [16] | Gottlob, Georg; Leone, Nicola; Scarcello, Francesco, Hypertree decompositions and tractable queries, J. Comput. System Sci., 64, 3, 579-627 (2002) · Zbl 1052.68025 |
| [17] | Gottlob, Georg, On minimal constraint networks, (Ho-Man Lee, Jimmy, CP. CP, Lecture Notes in Comput. Sci., vol. 6876 (2011), Springer), 325-339 · Zbl 1270.68268 |
| [18] | Gyssens, Marc; Jeavons, Peter; Cohen, David A., Decomposing constraint satisfaction problems using database techniques, Artificial Intelligence, 66, 1, 57-89 (1994) · Zbl 0803.68090 |
| [19] | Honeyman, Peter; Ladner, Richard E.; Yannakakis, Mihalis, Testing the universal instance assumption, Inform. Process. Lett., 10, 1, 14-19 (1980) · Zbl 0422.68048 |
| [20] | Houghton, Chris; Cohen, David A., Solution equivalent subquadrangle reformulations of constraint satisfaction problems, (van Beek, Peter, CP. CP, Lecture Notes in Comput. Sci., vol. 3709 (2005), Springer), 851 |
| [21] | Kautz, Henry A.; Selman, Bart, A general framework for knowledge compilation, (Boley, Harold; Richter, Michael M., PDK. PDK, Lecture Notes in Comput. Sci., vol. 567 (1991), Springer), 287-300 |
| [22] | Lecoutre, Christophe, Constraint Networks - Techniques and Algorithms (2009), John Wiley and Sons |
| [23] | Mackworth, Alan; Freuder, Eugene, The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, 25, 1, 65-74 (1985) |
| [24] | Maier, David, The Theory of Relational Databases (1983), Computer Science Press · Zbl 0519.68082 |
| [25] | Maier, David; Sagiv, Yehoshua; Yannakakis, Mihalis, On the complexity of testing implications of functional and join dependencies, J. ACM, 28, 4, 680-695 (1981) · Zbl 0481.68094 |
| [26] | Montanari, Ugo, Networks of constraints: Fundamental properties and applications to picture processing, Inform. Sci., 7, 95-132 (1974) · Zbl 0284.68074 |
| [27] | Montanari, Ugo; Rossi, Francesca, Fundamental properties of networks of constraints: A new formulation, (Kanal, L.; Kumar, V., Search in Artificial Intelligence (1988)), 426-449 |
| [28] | Olteanu, Dan; Koch, Christoph; Antova, Lyublena, World-set decompositions: Expressiveness and efficient algorithms, Theoret. Comput. Sci., 403, 2-3, 265-284 (2008) · Zbl 1203.68042 |
| [29] | Dan Olteanu, Jakub Zavodny, Factorised representations of query results, in: Proc. International Conference on Database Theory ICDT 2012, Berlin, Germany, March 26-30, 2012.; Dan Olteanu, Jakub Zavodny, Factorised representations of query results, in: Proc. International Conference on Database Theory ICDT 2012, Berlin, Germany, March 26-30, 2012. |
| [30] | Rodošek, Robert, A new approach on solving 3-satisfiability, (Calmet, Jacques; Campbell, John; Pfalzgraf, Jochen, Artificial Intelligence and Symbolic Mathematical Computation. Artificial Intelligence and Symbolic Mathematical Computation, Lecture Notes in Comput. Sci., vol. 1138 (1996), Springer: Springer Berlin, Heidelberg), 197-212 · Zbl 1541.68265 |
| [31] | Tsang, Edward, Foundations of Constraint Satisfaction (1993), Academic Press |
| [32] | Umans, Christopher; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto L., Complexity of two-level logic minimization, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 25, 7, 1230-1246 (2006) |
| [33] | Voronov, Alexey; Åkesson, Knut; Ekstedt, Fredrik, Enumeration of valid partial configurations, (Shchekotykhin, K.; Jannach, D.; Zanker, M., Proceedings IJCAI 2011 Workshop on Configuration. Proceedings IJCAI 2011 Workshop on Configuration, Barcelona, Spain, July 16, 2011. Proceedings IJCAI 2011 Workshop on Configuration. Proceedings IJCAI 2011 Workshop on Configuration, Barcelona, Spain, July 16, 2011, CEUR Workshop Proc., vol. 755 (2011)), paper 04, available at |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
