In 1936, Alan Turing proved the startling result that not all mathematical problems can be solved algorithmically. For those which can be, we still do not always know when there's a clever technique which could give us the answer quickly. In particular, the famous "P = NP" question asks whether, for problems where the correct solution has a proof which can easily be checked, in fact there's a quick way to find the answer.
Many difficult problems become easier if they have symmetries: finding the shortest route to deliver many parcels would be easy if all the houses were neatly arranged in a circle. This lecture will explore the interactions between symmetry and complexity.
Colva Roney-Dougal is Professor of Pure Mathematics at the University of St Andrews and Director of the Centre for Interdisciplinary Research in Computational Algebra.
Please email @email to register.
The lecture will be available on our Oxford Mathematics YouTube Channel on 12 October at 5 pm.
The Oxford Mathematics Public Lectures are generously supported by XTX Markets.