Intractabilitat

Capítols

1. 7.1
   Classes P i NP

   Problemes que es resolen en temps polinòmic i problemes on només sabem verificar una solució ràpid.

   Llegit
2. 7.2
   Reduccions i NP-completesa

   Reduir un problema a un altre permet comparar-ne la dificultat. Els problemes NP-complets són els més difícils de NP.

   Llegit
3. 7.3
   Consolidació

   Repàs de tot el tema en una sola pàgina: les idees clau de cada capítol, com encaixen entre elles i els errors més habituals. Ideal per repassar abans de l'examen.

   Llegit