Sumários
7-3-2022 (Aula 1)
- Apresentação da unidade curricular e modelo de avaliação.
- Breves notas sobre computabilidade
- A Hierarquia de Chomsky
- Determinismo vs não-determinismo
- Máquinas de Turing e a sua equivalência à luz da Computabilidade
- Com uma só fita
- Com várias fitas
- Determinísticas
- Não-determinísticas
- - Linguagens reconhecíveis - reconhecedores & enumeradores
- - Linguagens decidíveis - decisores
- - Noção de redução entre linguagens
- - $A_{TM}$ como problema indecidível (mas obviamente reconhecível)
14-3-2022 (Aula 2)
- Teorema de Rice
- Noção de História de Computação Positiva
- Loção de Linear Bounded Automata (LBA)
- O Post Correspondence Problem (PCP)
- Noção de complexidade computacional (no pior caso)
- Notação de Landau
- Conversão de TM de várias fitas em TM de uma só fita e sua consequência no tempo de execução
- A classe de complexidade P
- Conversão de TM não determinística em TM determinística
Um emulador muito simples de uma Máquina de Turing
21-3-2022 (Aula 3)
- A classe de complexidade NP
- Linguagens NP-completos
- Reduções polinomiais de linguagens ($A\leq_PB$)
- O Teorema de Cook-Levin (SAT é NP-completo)
- 3SAT é NP-completo (SAT$\leq_P$3SAT)
- Clique é NP-completo (3SAT $\leq_P$ Clique)
- VertexCover é NP-completo (3SAT $\leq_P$ VertexCover)
- HamPath e UHamPath são NP-completos (3SAT$\leq_P$HamPath e HamPath$\leq_P$UHamPath)
- Knapsack é NP-completo (3SAT$\leq_P$Knapsack)
28-3-2022 (Aula 4)
- Complexidade por espaço SPACE e NSPACE
- O teorema de Savitch (NSPACE$(f(n))\subseteq$SPACE$(f(n)^2)$)
- PSPACE e NPSPACE
- Linguagens PSPACE-completas
- TQBF é PSPACE-completa
4–4-2022 (Aula 5)
- GG é PSPACE-completa
- Complexidade sub-linear
- As classes L e NL
- PATH é NL-completa
- coNL=NL
9–5-2022 (Aula 6)
- Intratabilidade
- Teorema da hierarquia de espaço
- Teorema da hierarquia de tempo
16–5-2022 (Aula 7)
- Hierarquia Polinomial: $\Sigma^p_i$
- Complexidade de Circuitos
- Nova demonstração do Teorema de Cook-Levin
- A classe $\mathbf{P}_{/poly}$ e a possível contribuição da complexidade de circuitos para o $\mathbf{P}\neq \mathbf{NP}$
23–5-2022 (Aula 8)
- Computação probabilística
- Noção de $\mathbf{BPTime}[t]$
- A classe $\mathbf{BPP}$
- Teste probabilístico de primalidade
- Teste probabilístico de identidade de BDD
30–5-2022 (Aula 9)
- Mais algoritmos probabilísticos
- valor mediano de um conjunto
- identificação de polinómios dados por circuitos algébricos
- correspondências perfeitas em grafos bipartidos
- Provas interactivas determinísticas
- A classe $\mathsf{dIP}$
- Provas interactivas não determinísticas
- A classe $\mathsf{IP}$
- GNI$\in \mathsf{IP}$
- Provas $\mathsf{AM}$
- A classe $\mathsf{AM}$
- GNI$\in \mathsf{AM}$
6–6-2022 (Aula 10)
- Algoritmos aproximativos
- Complexidade do caso médio (segundo Levin)
- distP e distNP
- noção de distNP-completo
- Desaleatorização
Última modificação: 27/05/2025