COMP70005 Complexity

Autumn Term 2020

Timetable (provisional - subject to change)

Week Date ActivityTopicSlidesExercisesVideos
2 14 Oct Wed 10:00 interactive session Computational Models 1-61 1 1. Introduction 2.1 Tractable and intractable problems 2.2 Turing machines and decidable problems 2.3 Multi-tape Turing machines and P 2.4 Nondeterministic Turing machines and NP 2.5 The time hierarchy theorem
3 21 Oct Wed 10:00 interactive session Reduction and NP-completeness 62-93 2 3.1 NP 3.2 Reduction 3.3 NP-complete problems 3.4 2SAT in P
4 28 Oct Wed 10:00 interactive session NP-completeness continued, Approximation 94-134 3 3.5 Proof of the Cook-Levin Theorem 3.6 Travelling Salesman, NP-intermediate 3.7 Further NP-complete problems, strongly NP-complete 4 Approximation
5 4 Nov Wed 10:00 interactive session Space complexity 135-168 4 5.1 Space complexity classes 5.2 Relationships between time and space 5.3 Savitch's Theorem, Space Hierarchy Theorem 5.4 Complementary problems, Szelepscenyi-Immerman Theorem 5.5 Logspace reduction 5.6 Oracles and the polynomial hierarchy
6 11 Nov Wed 10:00 interactive session Parallel computation 169-212 5 6.1 Parallelizable problems 6.2 Max flow 6.3. Boolean circuits 6.4. Uniform circuit families 6.5. PRAMs 6.6. NC 6.7. Borodin's Theorem
7 18 Nov Wed 10:00 interactive session Randomised computation, Function problems 213-257 6 7.1 Prime numbers 7.2 Probabilistic computation 7.3 Monte Carlo algorithms 7.4 RP, ZPP and BPP 7.5 Examples, BQP 8.1 Function problems 8.2 FP, FNP, oracles
8 25 Nov Wed 10:00 interactive session Cryptography, Protocols 258-300 7 9.1 One-time pad 9.2 Public key cryptosystems, one-way functions 9.3 RSA 9.4 UP, RSA continued 10.1 Protocols 10.2 Zero-knowledge proofs 11 Concluding remarks
9 2 Dec Wed 10:00 revision session Revision
10 11 Dec Fri 14:00 Examination
11 7-11 Dec

Lecture slides - provisional

Exercises with answers (so far)

piazza

Introduction to the course

Computational complexity is the study of the computational resources required by algorithms. These resources are typically time and space. We would like to find the best possible algorithms for solving a given problem, i.e. the algorithms which use the least time (or space). For instance, we would like fast algorithms for sorting a list, or for finding the largest flow in a network, or verifying (model-checking) whether a particular property holds for a program.

We can use various techniques to analyse existing algorithms and state the time taken for a given input size (typically in worst-case or average-case). We then naturally ask whether these times can be improved. Such matters require much ingenuity and effort.

Complexity theory organises the problems into classes depending on the complexity of the algorithms so far known. Thus we get for instance the class of problems which are computable in polynomial time (P) and the class of those computable in polynomial space (PSPACE). There is always potential for improvement, in that we might discover that a problem which lies in a high-complexity class turns out to lie in a lower-complexity class. Such a thing happened with the problem of whether a number is prime. In 2002 this was shown to lie in P - previous algorithms required more than polynomial time. If the same were to happen with the problem of factorising a number, it would have profound implications for the security of public-key cryptosystems.

Within many complexity classes there are problems of particular interest, namely the complete problems. Their significance is that if you can find an algorithm for, say, a PSPACE-complete problem which runs in polynomial time, then all PSPACE problems have polynomial algorithms. Of course, since no one has managed to do this for any PSPACE-complete problem, if the problem you are considering is PSPACE-complete then you are fairly safe in assuming that there is no polynomial-time algorithm to solve it.

Even within P, the class of "easy" problems, we can make meaningful distinctions. For instance, we can ask whether we can use parallelism to speed up an algorithm significantly. It turns out that we can identify a class of problems within P for which this is possible. Other problems in P appear to lie outside this class, and therefore can only be solved in an inherently sequential fashion.

Complexity continues to be an active research area, as many, if not most, of the key questions remain unanswered. The most famous of these is the P=NP question. A prize of $1 million is now offered for its solution, either positively or negatively.

List of topics (provisional):