Sumários

P13 - Complexidade Computacional

5 janeiro 2024, 10:30 Pedro Tiago Monteiro

Resolução de exercícicos:
- Mostrar que Prob \in NP
- Mostrar que Prob \in NP-dificil


P13 - Complexidade Computacional

5 janeiro 2024, 10:30 Jan Gunnar Cederquist

Mostrar que Prob é NPC

  - Mostrar que Prob é NP  
  - Mostrar que Prob é NP-hard (reducão polinomiál)


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;