Professor Rick Thomas

In many cases it is clear that we can use a computer to solve a problem. For example, if we are trying to draw up a timetable, assigning lessons to timetable slots so that no student (or teacher) has to be in two places at once, we can systematically look at all the possibilities searching for a solution. It is not difficult to write a program that will correctly solve this problem. However, there is a significant issue here, in that, for any reasonable number of lessons to be timetabled, the program will take centuries to run, and is therefore of no practical use. There are several problems where this phenomenon arises, and we must be aware of how long our program will take to run. The idea of the talk is to give a gentle introduction to this subject (which is known as "computational complexity") so that people can get a flavour as to what the issues are. The talk may be of interest to mathematics students to see how mathematical techniques allow us to analyze such situations or to computer science students to see that there are problems for which there are no practical programs which can solve them.

• Approximate length: 50 minutes
• Equipment required: overhead projector
• Target audience: AS or A level students studying Mathematics or Computer Science