Abstract
We study two resolution-like refutation systems for finite-domain constraint satisfaction problems, and the efficiency of these and of common CSP algorithms. By comparing the relative strength of these systems, we show that for instances with domain size d, backtracking with 2-way branching is super-polynomially more powerful than backtracking with d-way branching. We compare these systems with propositional resolution, and show that every family of CNF formulas which are hard for propositional resolution induces families of CSP instances that are hard for most of the standard CSP algorithms in the literature.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, A.B.: Intelligent Backtracking on Constraint Satisfaction Problems: Experimental and Theoretical Results. PhD thesis, University of Oregon (1995)
Beame, P., Culberson, J., Mitchell, D.: The resolution complexity of random graph k-colourability (in preparation)
Beame, P., Impagliazzo, R., Sabharwal, A.: Resolution complexity of independent sets in random graphs. In: Proc., 16th Annual Conference on Computational Complexity (CCC), June 2001, pp. 52–68 (2001)
Beame, P., Karp, R., Pitassi, T., Saks, M.: On the complexity of unsatisfiability proofs for random k-CNF formulas. In: Proc. of the 30 Annual ACM Symp. on the Theory of Computing (STOC 1998), May 1998, pp. 561–571 (1998)
Beame, P., Kautz, H., Sabharwal, A.: Understanding the power of clause learning. In: Proc., Eighteenth Int’l. Joint Conferences on Artificial Intelligence (IJCAI 2003) (2003)(to appear)
Ben-Sasson, E., Wigderson, A.: Short proofs are narrow: Resolution made simple. In: Proc. of the 31st Annual Symp. on the Theory of Computation (STOC 1999), pp. 517–526 (May 1999) (also appears as ECCC report TR99-022)
Buresh-Oppenheim, J., Pitassi, T.: The complexity of resolution refinements. In: Proc., Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003), pp. 138–147 (2003)
Chvátal, V., Szemerédi, E.: Many hard examples for resolution. Journal of the ACM 35(4), 759–768 (1988)
Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. J. Symbolic Logic 44(1), 23–46 (1979)
De Kleer, J.: A comparison of ATMS and CSP techniques. In: Proc. of the 11th Int’l. Joint Conf. on A. I (IJCAI 1989), pp. 290–296 (1989)
Dechter, R.: From local to global consistency. Artificial Intelligence 55, 87–107 (1992)
Frost, D., Dechter, R.: Dead-end driven learning. In: Proc., Twelfth Nat. Conf. on Artificial Intelligence (AAAI 1994), pp. 294–300 (1994)
Goerdt, A.: Unrestricted resolution versus N-resolution. Theoretical Computer Science 93, 159–167 (1992)
Haken, A.: The intractability of resolution. Theoretical Computer Science 39, 297–308 (1985)
Kullmann, O.: Upper and lower bounds on the complexity of generalized resolution and generalized constraint satisfaction problems (2000) (manuscript)
Mitchell, D.G.: Hard problems for CSP algorithms. In: Proc., 15th Nat. Conf. on Artificial Intelligence (AAAI 1998), pp. 398–405 (1998)
Mitchell, D.G.: Resolution complexity of random constraints. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 295–309. Springer, Heidelberg (2002)
Molloy, M., Salavatipour, M.: The resolution complexity of random constraint satisfaction problems (submitted)
Schiex, T., Verfaillie, G.: Nogood recording for static and dynamic csp. In: Proc. of the IJCAI 1993/SIGMAN Workshop on Knowledge-based Production Planning, Scheduling and Control, August 1993, pp. 305–316 (1993)
Urquhart, A.: Hard examples for resolution. Journal of the ACM 34(1), 209–219 (1987)
Urquhart, A.: Resolution proofs of matching principles. Annals of Mathematics and Artificial Intelligence (2002) (to appear)
Walsh, T.: SAT vs CSP. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 441–456. Springer, Heidelberg (2000)
Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. of Artificial Intelligence Research 12, 93–103 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mitchell, D.G. (2003). Resolution and Constraint Satisfaction. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive