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

  Hopcroft, John E., 1939-

  3rd ed./Pearson International Edition., Pearson/Addison-Wesley

• Computational complexity

  Papadimitriou, Christos H.

  Addison-Wesley

• Handbook of theoretical computer science. Vol. A, Algorithms and complexity / edited by Jan van Leeuwen.

  Elsevier

• A first course in computability

  Rayward-Smith, V. J.

  McGraw-Hill

• Introduction to the theory of complexity

  Bovet, Daniel Pierre.

  Prentice Hall

• Introduction to the theory of computation

  Sipser, Michael, author.

  Third edition.; International edition., Place of publication not identified : Cengage Learning

• The golden ticket : P, NP, and the search for the impossible

  Fortnow, Lance, 1963-

  Princeton University Press

• Computational complexity : a modern approach

  Arora, Sanjeev.

  Cambridge University Press

• Computational complexity : a conceptual perspective

  Goldreich, Oded.

  Cambridge University Press

• Mathematics and computation

  Wigderson, Avi,

  Princeton University Press

Module leaders

Dr Iain Phillips