Where the hard computational problems are?

Speaker:  Toby Walsh – Kensington, NSW, Australia
Topic(s):  Artificial Intelligence, Machine Learning, Computer Vision, Natural language processing


Some computational problems are easy. We can sort numbers quickly for example. Other problems are hard. Scheduling jobs, routing trucks, these are all hard problems to solve. I will survey research in Artificial Intelligence that helps find where hard computational problems can be found, and throws some light on what makes some problems hard and others easy. Computational complexity gives us some tools (for example, big O analysis and complexity classes) but much of my talk will come from an unusual direction - statistical mechanics. Surprisingly, phase transition behaviour observed in nature is also observed in computation, and problem hardness can often be found at phase boundaries. The talk will be richly illustrated with many examples of such behaviour.

About this Lecture

Number of Slides:  45
Duration:  45 - 60 minutes
Languages Available:  English
Last Updated: 

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.