Sumários
Aula 12
23 Maio 2023, 10:00 • Isabel Gama Nunes
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.
Aula 11
16 Maio 2023, 10:00 • Isabel Gama Nunes
Undecidability (cont.).
Reducibility.
(Sipser's book, Chapter 5)
Aula 10
9 Maio 2023, 10:00 • Isabel Gama Nunes
Universal Turing machines.
Examples of decidable languages.
(Sipser's book, Section 4.1)
Undecidability
(Sipser's book, Chapter 5)
Third individual evaluation test.
Aula 9
2 Maio 2023, 10:00 • Isabel Gama Nunes
Variants of Turing machines.
Algorithms and Turing machines.
(Sipser's book, Sections 3.2, 3.3)
Examples of decidable languages.
Operations with decidable languages.
(Sipser's book, Section 4.1)