Computational Complexity

INFR11102 - Spring 2018

General Information


The goal of computational complexity is to classify computational problems according to their intrinsic difficulty or “complexity”. It complements algorithms as we will be aiming to provide “lower bounds” to various problems. Among other things, we will talk about why the P vs. NP problem, one of the seven Millennium Prize Problems, is important, intriguing, and difficult!

Some recommended (but not required) readings:

In particular, the Arora-Barak book is available through the library (EASE account required). Most material we will cover can be found in this book.

Lecture Notes

Will be uploaded after lectures.

Problem Sets

There will be two problem sets. The first one is for feedback only and the second one for credits.


Please read the following guidelines regarding coursework: