## 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

### Pre-requisites

The contents of CO240 Models of Computation

### 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 Piazza 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.

### Supplementary

• #### Introduction to automata theory, languages, and computation

Hopcroft, John E., 1939-

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.

2nd, International ed., Brooks Cole

• #### Introduction to the theory of computation / Michael Sipser

Sipser, Michael ; Sipser, Michael

South-Western

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

Fortnow, Lance, 1963-

Princeton University Press

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

Fortnow, Lance, 1963-, author.

Princeton, New Jersey ; Woodstock, Oxfordshire : Princeton University Press

• #### Computational complexity : a modern approach

Arora, Sanjeev.

Cambridge University Press