T25 - Complexidade computacional (cont.)
31 maio 2021, 14:00 • Pedro Tiago Monteiro
Exemplos de demonstração de problemas NP-Completos: CNFSAT, 3CNFSAT.
Exemplo de problemas polinomiais: 2CNFSAT.
Reduções: 3CNFSAT<=IndepSet, IndepSet<=CLIQUE, IndepSet<=VertexCover, VertexCover<=SetCover.