Sumários
Complexity - Abstract complexity
14 outubro 2014, 17:30 • 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
9 outubro 2014, 17:30 • Paulo Alexandre Carreira Mateus
P/Poly. Polynomial hierarchy.
Complexity - P and NP
7 outubro 2014, 17:30 • Paulo Alexandre Carreira Mateus
Time complexity. P and NP. NP-complete problem. Cook's theorem.
Computability - Reducibility
2 outubro 2014, 17:30 • Paulo Alexandre Carreira Mateus
m-reducibility, m-completeness. Effective non-listability. Post's coonstruction. Myhill's theorem. Relative computability and T-reducibility.
Computability - Abstract formalisms of computability
30 setembro 2014, 17:30 • Paulo Alexandre Carreira Mateus
Turing machines. Mu-recursive functions. Uniform famility of Boolean circuits.