Sumários
P13 - Complexidade Computacional
5 janeiro 2024, 10:30 • Pedro Tiago Monteiro
P13 - Complexidade Computacional
5 janeiro 2024, 10:30 • Jan Gunnar Cederquist
Mostrar que Prob é NPC
P13 - Complexidade Computacional
4 janeiro 2024, 15:30 • Francisco Gouveia
Resolução de exercícios:
- Mostrar que P está em NP;
- Mostrar que P está em NP-Difícil;
T20 - Complexidade computacional (cont.)
4 janeiro 2024, 14:00 • Pedro Tiago Monteiro
Exemplos de reduções ("aula prática") adicionais aos slides:
- 3CNFSAT<= Independent Set (ISET)
- ISET <= CLIQUE
P13 - Complexidade Computacional
4 janeiro 2024, 12:30 • Francisco Gouveia
Resolução de exercícios:
- Mostrar que P está em NP;
- Mostrar que P está em NP-Difícil;