Computability and Computational Complexity
| Code | School | Level | Credits | Semesters |
| COMP3001 | Computer Science | 3 | 10 | Autumn UK |
- Code
- COMP3001
- School
- Computer Science
- Level
- 3
- Credits
- 10
- Semesters
- Autumn UK
Summary
You will begin by considering the attempts to characterise the problems that can theoretically be solved by physically possible computational processes, along with the practical implications. You will then consider the area of complexity theory, looking at whether or not problems can be solved under limitations on resources such as time or space. You will examine the classes P and NP, and how to show problems are NP-complete. You will also consider other practically important classes such as: PSPACE and its relevance to adversarial games, and NC and its relevance to understanding of parallel computation and the limitations of its effectiveness. You will also consider classes BPP for probabilistic computation, and BQP for quantum computing, along with ideas of post-quantum cryptography based on NP-hard problems. You will look at the practical implications of computability and complexity in the context of real-world problems, such as vehicle routing, scheduling, timetabling, machine learning, and quantum computing.
Target Students
Available to Level 3 and Level 4 students in the School of Computer Science. This module is part of the Foundations of Computer Science theme in the School of Computer Science.
Assessment
- 20% Coursework 1: Continuous assessment. Assessment(s) may be under invigilated in-class test conditions. Reassessment is 100% examination.
- 80% Exam 1 (2-hour): Written examination. Reassessment is 100% examination.
Assessed by end of autumn semester
Educational Aims
The overall aim of the course is to provide an understanding of the concepts of computability and computational complexity.In particular, courseobjectives are as follows:To provide an appreciation of the many attempts that have been made to define the class of computable functions and to indicate that all the sensible attempts to do this have been shown to be equivalent.To appreciate impossibility proofs based upon diagonalisation arguments.To introduce the fact that there are problems that cannot possibly be solved on a computer.To show how, apparently different, computable problems of practical importanceare related in respect of their algorithmic complexity and how this relates to the design and choices of algorithms for solving them in standard classical computers and also quantum computers.Learning Outcomes
Knowledge and Understanding
- To understand the theory of computation via mathematical methods.
Intellectual Skills
- To apply and deploy mathematical ability, practices and tools;
- To understand and logically evaluate the problems in computability and complexity;
- To think independently about the issues while giving due weight to previous work;
- To understand the ideas of the theory of computability and complexity and relate them to particular problems.
Professional Skills
- To extend their own abilities by specialising or generalising from their previous knowledge.
Transferable Skills
- The ability to solve problems using mathematics, by consulting external sources if necessary.