| Unit name | Computational Complexity |
|---|---|
| Unit code | COMS30126 |
| Credit points | 10 |
| Level of study | H/6 |
| Teaching block(s) |
Teaching Block 2 (weeks 13 - 24) |
| Unit director | Professor. Jozsa |
| Open unit status | Not open |
| Pre-requisites |
EMAT10702, COMS21101 or MATH1150 |
| Co-requisites |
None |
| School/department | Department of Computer Science |
| Faculty | Faculty of Engineering |
This unit aims to develop an understanding of basic notions of computational complexity for deterministic, probabilistic and non-deterministic algorithms. The Turing machine and Boolean circuit models of computation will be introduced and used to study fundamental complexity classes including P, PSPACE, NP, L, NL, BPP. Further aspects of the famous P vs NP problem will be discussed.
