Complexity. Measuring complexity. The Big-O notation.

The class P. Examples of problems in P.

The class NP. Examples of problems in NP.

The P versus NP question.

Polinomial time reducibility.

NP-completeness. Examples of NP-complete problems.

Rice's theorem.

Back to the P versus NP question.

(Sipser's book, Sections 7.1 to 7.4)

4th individual evaluation test.