Ïã¸ÛÁùºÏ²Ê

Aims:

The module addresses the theoretical and practical limitations of computation and provides a mathematical framework for proving properties of programs. The concepts of undecidability and intractability are formally introduced and discussed through a number of examples. The module will convey the proof techniques that are used to classify problems. It is intended that students learn how to apply them to classify unfamiliar problems for themselves.

Intended learning outcomes:

On successful completion of the module, a student will be able to:

1. Analyse the complexity of a variety of problems and algorithms.
2. Prove that a problem is undecidable.
3. Prove the equivalence of different models of computation.
4. Find a polynomial time reduction from one problem to another.
5. Determine the complexity class of a decidable problem.
6. Categorise the complexity of a language.

Indicative content:

The following are indicative of the topics the module will typically cover:

Models of Computation:

• Deterministic Turing machines.
• Alternative models: variations of the concept of Turing machine.
• Alternative models: register machines, imperative programming languages.

Languages:

• Language acceptance.
• Language recognition.
• Decidable and Recognisable languages.
• Closure properties of languages.

Undecidability:

• The Halting Problem and other unsolvable problems.
• Problem reduction.
• Rice’s Theorem.
• Cantor’s diagonal argument and the cardinality of unrecognisable languages.
• Undecidability of the tiling problem.
• Undecidability of first-order logic and incompleteness of arithmetic.

Basic Concepts of Complexity Theory:

• Tractable and intractable problems and algorithms.
• Definition of Time Complexity.
• Decision vs Optimisation Problems.
• Travelling Salesman and its variants.

Polynomial-time reduction:

• Definition and properties.
• Lemmas and proofs.
• Hamiltonian Graphs and Travelling Salesman.

Complexity classes:

• Non-deterministic Turing machines.
• P, NP, and NP-complete classes.
• Complement and Co-Complete Classes.

Proving NP-hardness:

• Cook’s theorem.
• Satisfiability and its variants.
• Reductions between variants.

Other Complexity Classes:

• Space complexity, PSPACE, and PSPACE-Completeness.
• Savitch’s theorem.
• Logarithmic space.
• Time and space hierarchy theorems.
• Exponential time and hardness.
• Probabilistic classes.
• Approximation algorithms and hardness.

Requisites:

To be eligible to select this module as optional or elective, a student must: (1) be registered on a programme and year of study for which it is a formally available; and (2) have passed Theory of Computation (COMP0003), Algorithms (COMP0005), and Logic and Database Theory (COMP0009).