摘要: In a minimal binary constraint network, every tuple of relation can be extended to solution. The tractability or intractability computing solution such network was long standing open question. Dechter conjectured this computation problem NP-hard. We prove conjecture. also conjecture by and Pearl stating that for k>=2 it is NP-hard decide whether single decomposed into an equivalent k-ary network. show holds even in case bi-valued constraints where k>=3, which proves another Pearl. Finally, we establish the frontier with respect domain cardinality parameter k.
core.ac.uk
harvard.edu
sci-hub.se 参考文章(32)
Christian Bessiere, Constraint Propagation Handbook of Constraint Programming. ,vol. 2, pp. 29- 83 ,(2006) , 10.1016/S1574-6526(06)80007-6
Ugo Montanari, Francesca Rossi, Fundamental Properties of Networks of Constraints: A New Formulation Search in Artificial Intelligence. pp. 426- 449 ,(1988) , 10.1007/978-1-4613-8788-6_12
Christophe Lecoutre, Constraint Networks: Techniques and Algorithms Wiley-IEEE Press. pp. 592- ,(2009)
Henry Kautz, Bart Selman, A General Framework for Knowledge Compilation PDK '91 Proceedings of the International Workshop on Processing Declarative Knowledge. pp. 287- 300 ,(1991) , 10.1007/BFB0013538
Samson Abramsky, Relational Hidden Variables and Non-Locality Studia Logica. ,vol. 101, pp. 411- 452 ,(2013) , 10.1007/S11225-013-9477-4
Chris Houghton, David Cohen, Solution Equivalent Subquadrangle Reformulations of Constraint Satisfaction Problems Principles and Practice of Constraint Programming - CP 2005. pp. 851- 851 ,(2005) , 10.1007/11564751_89
Martin Gebser, Benjamin Kaufmann, Torsten Schaub, Solution Enumeration for Projected Boolean Search Problems Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. pp. 71- 86 ,(2009) , 10.1007/978-3-642-01929-6_7
Robert Rodošek, A new approach on solving 3-satisfiability Artificial Intelligence and Symbolic Mathematical Computation. pp. 197- 212 ,(1996) , 10.1007/3-540-61732-9_59
Martin Gebser, Benjamin Kaufmann, André Neumann, Torsten Schaub, Conflict-driven answer set enumeration international conference on logic programming. pp. 136- 148 ,(2007) , 10.1007/978-3-540-72200-7_13
Marco Cadoli, Francesco M. Donini, A survey on knowledge compilation Ai Communications. ,vol. 10, pp. 137- 150 ,(1997)