Sumários
T12: Polynomial hierarchy
3 novembro 2017, 10:00 • Paulo Alexandre Carreira Mateus
Relative complexity. Polynomial hierarchy.
T11: Other NP complete problems
31 outubro 2017, 11:00 • Paulo Alexandre Carreira Mateus
NP complete problems. 3-Sat and Graph colouring.
T10: Complexity - P and NP
27 outubro 2017, 10:00 • Paulo Alexandre Carreira Mateus
NP-complete problem. Cook's theorem.
T9: Linear Compression
24 outubro 2017, 11:00 • Paulo Alexandre Carreira Mateus
Linear compression and Speedup. Constructible functions. Basic separation results.
T8: Complexity - basic concepts
20 outubro 2017, 10:00 • Paulo Alexandre Carreira Mateus
Time complexity and Space complexity. Tape reduction, non-deterministic Turing machine.