Complexity
Module aims
In this module you will have the opportunity to:
- study time and space complexity classes
- identify the complexity classes associated with computational problems
- prove that problems are complete for particular complexity classes
- develop the ability to fit a particular problem into a class of related problems, and so to appreciate the efficiency attainable by algorithms to solve the particular problem
- study circuit complexity and the class NC of parallelisable problems
- study randomised computation and the associated complexity classes
- explore how the P=NP problem is related to cryptography
Learning outcomes
Upon successful completion of this module you will be able to:
- determine to which complexity class a computational problem belongs
- prove that a computational problem is complete for a class such as NP
- establish and reason about properties of complexity classes
- demonstrate to what extent an NP-complete problem has efficient approximate solutions
- determine whether a problem has efficient parallel solutions
- evaluate the relationships between public key cryptography, one-way functions and the P=NP problem
Module syllabus
- Turing machines, decidability, machine independence
- Time complexity: the classes P and NP, NP-completeness, example problems from logic and graphs
- Space complexity classes
- The polynomial hierarchy
- The parallel computation thesis, Boolean circuits, PRAMs, the class NC
- Probabilistic algorithms
- Function problems
- One-way functions and cryptography
Teaching methods
The material will be taught through traditional lectures and tutorial sessions. You will be set unassessed exercises designed to reinforce the material as it is taught. Approximately half of these exercises will be discussed in class; the remainder are intended for you to use for self-study. You will be able to participate in further discussion via the online forum.
Assessments
There will be one written coursework that contributes 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks.
Written and verbal feedback will be given on the assessed coursework.
Reading list
Supplementary
-
Introduction to automata theory, languages, and computation
3rd ed./Pearson International Edition., Pearson/Addison-Wesley
-
Computational complexity
Addison-Wesley
-
Handbook of theoretical computer science. Vol. A, Algorithms and complexity / edited by Jan van Leeuwen.
Elsevier
-
A first course in computability
McGraw-Hill
-
Introduction to the theory of complexity
Prentice Hall
-
Introduction to the theory of computation
Third edition.; International edition., Place of publication not identified : Cengage Learning
-
The golden ticket : P, NP, and the search for the impossible
Princeton University Press
-
Computational complexity : a modern approach
Cambridge University Press
-
Computational complexity : a conceptual perspective
Cambridge University Press
-
Mathematics and computation
Princeton University Press