Sexta semana del curso Automata. Aunque pocas, las lecturas fueron largas. La primera video lectura se dedicó a los problemas intratables. Así, se revisaron los temas:

• Máquinas de Turing limitadas por tiempo.
• Las clases de problemas P y NP.
• Reducciones de tiempo polinomial.

Y, sí, lo confieso. Ya aquí ya estoy perdido. Debo repetir el curso para poder entender esta parte. La segunda lectura se dedicó al problema de satisfacilidad y el teorema de Cook. La última lectura se dedicó a:

• NP hard problems.
• El problema de la tautología.
• Cobertura de nodos.
• Knapsack.

Muy buen curso. Recomendable ampliamente.