I know the computer can solve this but how long will it take?

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

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc  seadmissions@le.ac.uk
E: MSc  pgadmissions@le.ac.uk

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604
E: csadmin@mcs.le.ac.uk

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom

Accessibility

DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.