Dr Holger Spakowski
20 credits / 30 lectures
This module, which is geared towards students in both Mathematics and Computer Science, provides an introduction to major topics in computational complexity theory, which is one of the core areas of theoretical computer science. In computational complexity, we investigate the power of efficient computation. That is, we try to distinguish between computational problems that can be solved efficiently in practice and those that, though theoretically solvable, are not solvable in practice because of prohibitively large time or space requirements. The central open problem is the P versus NP problem.