Abstract
The challenge to solve worst-case intractable computational problems lies at the core of much of the work in the constraint programming community. The traditional approach in computer science towards hard computational tasks is to identify subclasses of problems with interesting, tractable structure. Linear programming and network flow problems are notable examples of such well structured classes. Propositional Horn theories are also a good example from the domain of logical inference. However, it has become clear that many real-world problem domains cannot be modeled adequately in such well-defined tractable formalisms. Instead richer, worst-case intractable formalisms are required. For example, planning problems can be captured in general propositional theories and related constraint formalisms and many hardware and software verification problems can similarly be reduced to Boolean satisfiability problems. Despite the use of such inherently worst-case intractable representations, ever larger real-world problem instances are now being solved quite effectively. Recent state-of-the-art satisfiability (SAT) and constraint solvers can handle hand-crafted instances with hundreds of thousands of variables and constraints. This strongly suggests that worst-case complexity is only part of the story. I will discuss how notions of typical case and average case complexity can lead to more refined insights into the study and design of algorithms for handling real-world computationally hard problems. We will see that such insights result from a cross-fertilization of ideas from different communities, in particular, statistical physics, computer science, and combinatorics.
Work supported in part by the Intelligent Information Systems Institute at Cornell University sponsored by AFOSR (F49620-01-1-0076) and an NSF ITR grant (IIS-0312910).
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
Hogg, T., Huberman, B., Williams, C.: Phase Transitions and Search Problems. Artificial Intelligence 81(1-2), 1–15 (1996)
Kirkpatrick, S., Selman, B.: Statistical physics and computational complexity. In: Ong, N.P., Bhatt, R.N. (eds.) More is different – fifty years of condensed matter physics, Princeton University Press, Princeton (2001)
Gomes, C., Selman, B.: Satisfied with Physics. Science 297, 784–785 (2002)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining Computational Complexity from Characteristic Phase Transitions. Nature 400(8), 133–137 (1999)
Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D.: Rigorous results for (2+p)-sat. Theo. Comp. Sci. 265, 109–129 (2001)
Gomes, C.P., Selman, B., Crato, N., Kautz, H.: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J. Autom. Reas. 24 (2000)
Williams, R., Gomes, C., Selman, B.: Backdoors to Typical Case Complexity. In: Proc. IJCAI 2003 (2003)
Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solutions to random satisfiability problems. Science 297, 812–815 (2002)
Selman, B., Kautz, K., Cohen, B.: Local Search Strategies for Satisfiability Testing, DIMACS Series in Discr. Math. and Theor. Comp. Sci., vol. 26 (1993)
Wei, W., Erenrich, J., Selman, B.: Towards Efficient Sampling: Exploiting Random Walk Strategies. In: Proc. AAAI 2004 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Selman, B. (2004). Algorithmic Adventures at the Interface of Computer Science, Statistical Physics, and Combinatorics. In: Wallace, M. (eds) Principles and Practice of Constraint Programming – CP 2004. CP 2004. Lecture Notes in Computer Science, vol 3258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30201-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-30201-8_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23241-4
Online ISBN: 978-3-540-30201-8
eBook Packages: Springer Book Archive