Sumários
Class Fourteen
3 Junho 2025, 10:00 • Isabel Gama Nunes
The class NP. Examples of problems in NP.
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)
Class Thirteen
27 Maio 2025, 10:00 • Isabel Gama Nunes
Temporal complexity. Measuring complexity. Assymptotic analysis; the Big-O notation.
The class P.
(Sipser book, Sections 7.1, 7.2)
4th individual evaluation test.
Class Twelve
20 Maio 2025, 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)
Class Eleven
13 Maio 2025, 10:00 • Isabel Gama Nunes
Undecidability
Reducibility.
(Sipser's book, Chapter 5)
Class ten
6 Maio 2025, 10:00 • Isabel Gama Nunes
Operations with decidable languages.
Closure of the class of decidable languages and of recognizable languages under the union operation.
Universal Turing machines.
(Sipser's book, Section 4.1)
Third individual evaluation test.