Sumários
Complexity - Abstract complexity
13 outubro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Lectured by David Henriques. Resource-bounded proper universal functions. Abstract computation and certifications classes. Karp and Cook reducibility. Computation time as a resource. Computation space as a resourece.
Complexity - Polynomial hierarchy
8 outubro 2015, 14:00 • Paulo Alexandre Carreira Mateus
P/Poly. Polynomial hierarchy.
Complexity - P and NP
6 outubro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Time complexity. P and NP. NP-complete problem. Cook's theorem.
Computability - Reducibility
1 outubro 2015, 14:00 • Paulo Alexandre Carreira Mateus
m-reducibility, Effective non-listability. Post's coonstruction. Myhill's theorem. Relative computability and T-reducibility.
Computability - Main theorems II
29 setembro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Myhill-Shepherdson theorem. Kleene's least fixed point theorem. Recursion theorem.