Sumários
Aula13
26 Maio 2026, 10:00 • Isabel Gama Nunes
The P versus NP question.
Polinomial time reducibility.
NP-completeness. Examples of NP-complete problems.
The Cook-Levin theorem.
(Sipser's book, Sections 7.1 to 7.4)
4th individual evaluation test.
Aula12
19 Maio 2026, 10:00 • Isabel Gama Nunes
Temporal complexity. Measuring complexity. Assymptotic analysis; the Big-O notation.
The class P.
The class NP. Examples of problems in NP.
The P versus NP question.
(Sipser book, Sections 7.1, 7.2, 7.3)
Aula11
12 Maio 2026, 10:00 • Isabel Gama Nunes
Undecidability (cont.). Some exercises.
Rice's theorem.
(Sipser book, Chapter 5)
Variants of Turing machines. The class of languages these variants recognize is the same as the original, deterministic, uni-tape model does.
(Sipser book, Sections 7.1, 7.2)
Aula10
5 Maio 2026, 10:00 • Isabel Gama Nunes
Undecidability.
Reducibility.
(Sipser's book, Chapter 5)
Third individual evaluation test.