What is an “efficient” algorithm? Can every algorithmic task be solved efficiently? Or are there inherently hard problems? Computational complexity provides a rigorous, mathematical foundation to reason about problems like these. In this course, we will discuss basic concepts like machine models, asymptotic time and space complexity, and important complexity classes such as P, NP, and BPP. We will illustrate these concepts with a number of practical examples, ranging from integer arithmetic to more advanced tasks like primality testing. The course also provides an outlook to applications of computational complexity theory, with a view towards cryptography; in particular, we will exhibit the power of one-way functions as a tool to build cryptographic systems.
Voorkennis
Introductory courses on algebra and probability theory.
Literatuur
Will be announced on the course webpage: http://www.cwi.nl/crypto/teaching.html
Toetsing
Graded home work exercises.