The theory and practice of solving intractable problems

Moore Building Auditorium

Professor Magnus Wahlström
School of Engineering, Physical and Mathematical Sciences

For well over 60 years, computer scientists have grappled with the question of the limits of computing for efficient problem solving. By now, although little has been proven mathematically, there is a broad consensus that for a large class of highly relevant tasks (such as scheduling problems, business optimisation problems, verification of digital circuits, and more), there probably is no efficient universal method. However, this clashes dramatically with an everyday industrial experience where such problems are regularly solved at scale. Professor Wahlström will review this apparent contradiction, known broadly as the P-vs-NP question, and discuss attempts towards its resolution.

Inaugural Lecture

Admission is free but booking is essential.

Professor Magnus Wahlstrom