好色tv

- Academic Registry


CM52038: Computational complexity

[Page last updated: 22 April 2025]

Academic Year: 2025/26
Owning Department/School: Department of Computer Science
Credits: 5 [equivalent to 10 CATS credits]
Notional Study Hours: 100
Level: Masters UG & PG (FHEQ level 7)
Period:
Semester 1
Assessment Summary: EXCB 100%
Assessment Detail:
  • Closed-book written examination (EXCB 100% - Qualifying Mark: 40)
Supplementary Assessment:
Like-for-like reassessment (where allowed by programme regulations)
Requisites: In taking this module you cannot take CM32025 OR take CM30073
Before taking this module you must take CM22008 AND ( take CM12006 OR take MA12013 ) OR ( take CM20254 AND take CM20217 AND take CM10312 )
Learning Outcomes: 1. To recognize NP-hard problems and prove the appropriate reductions. 2. To cope with NP-complete problems. 3. To know some fundamental methods of proving lower complexity bounds. 4. To understand the basics of quantum computing. 5. To be able to read, understand, critically evaluate and report instances of modern literature on the subject of the unit.


Synopsis: "You will explore the key concepts and mathematical techniques of computational complexity. You will learn to recognize and prove that problems are NP-hard, including the central concept of NP completeness, and consider a range of examples of NP-complete problems. You will learn to prove complexity lower bounds for some models of computations (e.g., algebraic computation trees). You will explore the basics of quantum computing. "

Content: Complexity: deterministic and non-deterministic Turing machines, the complexity class NP, versions of reducibility, NP-hardness and NP-completeness, examples of NP-complete problems (such as the satisfiability problem for Boolean formulae, clique, vertex cover, travelling salesman, subgraph isomorphism), polynomial-time approximation algorithms for NP-complete graph problems such as travelling salesman, lower complexity bounds, algebraic computation trees and their complexities, introduction to quantum computing (definitions, Deutsch and Deutsch-Jozsa algorithms).

Course availability:

CM52038 is Optional on the following courses:

Department of Computer Science
  • USCM-AFM01 : MComp(Hons) Computer Science (Year 4)
  • USCM-AAM02 : MComp(Hons) Computer Science with Study year abroad (Year 5)
  • USCM-AKM02 : MComp(Hons) Computer Science with Year long work placement (Year 5)
  • USCM-AFM27 : MComp(Hons) Computer Science and Artificial Intelligence (Year 4)
  • USCM-AAM27 : MComp(Hons) Computer Science and Artificial Intelligence with Study year abroad (Year 5)
  • USCM-AKM27 : MComp(Hons) Computer Science and Artificial Intelligence with Year long work placement (Year 5)

Notes:

  • This unit catalogue is applicable for the 2025/26 academic year only. Students continuing their studies into 2026/27 and beyond should not assume that this unit will be available in future years in the format displayed here for 2025/26.
  • 好色tv and units are subject to change in accordance with normal University procedures.
  • Availability of units will be subject to constraints such as staff availability, minimum and maximum group sizes, and timetabling factors as well as a student's ability to meet any pre-requisite rules.
  • Find out more about these and other important University terms and conditions here.