Computability and Intractability (U01897)

? Credit Points : 10 ? SCQF Level : 9 ? Acronym : INF-3-CI

The course centres around the so-called Church-Turing Thesis which proposes that each one of a variety of different formal systems adequately captures the intuitive concept of (effective) computability. This thesis implies that by studying any one of these systems, for example Turing machines, we can learn about the inherent theoretical limitations of computers. If a problem cannot be solved by a Turing machine, then there is no computable solution to it at all.

Not all the computational problems which can be solved in principle can be solved in practice: the computational resources required (time or space) may be prohibitive. This observation motivates the study of resource-bounded computation. Having accepted an extended version of the Church-Turing thesis (that the computationally tractable problems are those which can be efficiently solved by a Turing machine) we are led inevitably to conclude the existence of natural problems which can be solved in principle but not within any reasonable resource bound.

The fundamental concepts and techniques encountered in this course resonate around the whole of Computer Science and indeed beyond: effective procedures and decidability, simulation methods, machine encodings and universality, diagonalization arguments, and reductions between problems.

Entry Requirements

? Pre-requisites : Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School.

Subject Areas

Home subject area

Theoretical Computer Science, (School of Informatics, Schedule O)

Delivery Information

? Normal year taken : 3rd year

? Delivery Period : Semester 2 (Blocks 3-4)

? Contact Teaching Time : 3 hour(s) per week for 10 weeks

First Class Information

Date	Start	End	Room	Area	Additional Information
08/01/2007	10:00	10:50	Lecture Room 5326, JCMB	KB

All of the following classes

Type	Day	Start	End	Area
Lecture	Monday	10:00	10:50	KB
Lecture	Thursday	10:00	10:50	KB

Summary of Intended Learning Outcomes

It is anticipated that students who successfully complete the course will be able to:
- Discuss the fundamental nature of computating as a process(Turing's Thesis).
- Discuss the limits to computing both in absolute terms (unsolvable problems) and practical terms (intractable problems).
- Distinguish different types of languages (recursively enumerable, recursive etc.).
- Demostrate the solvability of a given problem both in informal as well as formal terms (use of Turing machines).
- Demostrate the unsolvability of a given problem both in informal as well as formal terms (use of reductions).
- Discuss the classification of solvable problems into tractable versus intractable ones (P versus NP).
- Judge when a problem is likely to be intractable.
- Discuss the notion of polynomial time reduction and its relevance to classifying the relative complexity of problems.
- Demostrate the likely intractability of a given problem by relating it to other known problems (use of polynomial time reductions).