CM32025: 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: | Honours (FHEQ level 6) |
| 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 CM52038
Before taking this module you must ( take AT LEAST 1 MODULE FROM {CM12006, MA12013} AND take CM22008 ) OR ( take CM10312 AND take CM20256 AND take CM10227 AND take CM20254 AND take CM20217 )
|
| Learning Outcomes: |
- 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.
|
| 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: |
CM32025 is Optional on the following courses:
Department of Computer Science
- USCM-AFB30 : BSc(Hons) Computer Science (Year 3)
- USCM-AAB07 : BSc(Hons) Computer Science with Study year abroad (Year 4)
- USCM-AKB07 : BSc(Hons) Computer Science with Year long work placement (Year 4)
- USCM-AFB31 : BSc(Hons) Computer Science and Artificial Intelligence (Year 3)
- USCM-AAB27 : BSc(Hons) Computer Science and Artificial Intelligence with Study year abroad (Year 4)
- USCM-AKB27 : BSc(Hons) Computer Science and Artificial Intelligence with Year long work placement (Year 4)
- USCM-AFB32 : BSc(Hons) Computer Science and Mathematics (Year 3)
- USCM-AAB20 : BSc(Hons) Computer Science and Mathematics with Study year abroad (Year 4)
- USCM-AKB20 : BSc(Hons) Computer Science and Mathematics with Year long work placement (Year 4)
- USCM-AFM30 : MComp(Hons) Computer Science (Year 3)
- USCM-AFM31 : MComp(Hons) Computer Science and Artificial Intelligence (Year 3)
- USCM-AKM31 : MComp(Hons) Computer Science and Artificial Intelligence with professional placement (Year 3)
- USCM-AKM31 : MComp(Hons) Computer Science and Artificial Intelligence with study abroad (Year 3)
- USCM-AFM32 : MComp(Hons) Computer Science and Mathematics (Year 3)
- USCM-AKM32 : MComp(Hons) Computer Science and Mathematics with professional placement (Year 3)
- USCM-AKM32 : MComp(Hons) Computer Science and Mathematics with study abroad (Year 3)
- USCM-AKM30 : MComp(Hons) Computer Science with professional placement (Year 3)
- USCM-AKM30 : MComp(Hons) Computer Science with study abroad (Year 3)
|
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.
|
