Complejidad y Computabilidad

Los MDM de esta asignatura, junto con sus transparencias minimalistas en PDF para imprimirlas e irlas rellenando mientras se ven dichos MDM, son:

• Mini-vídeo «Ejemplo 1 de PCP y PCPM». Se describe un ejemplo de PCP y PCPM y se estudia si admite o no solución positiva: [Transparencias minimalistas de «Ejemplo 1 de PCP y PCPM»]
• Mini-vídeo «Ejemplo 2 de PCP y PCPM». Se describe otro ejemplo de PCP y PCM y se estudia si admite o no solución positiva: [Transparencias minimalistas de «Ejemplo 2 de PCP y PCPM»]
• Mini-vídeo «Ejemplo de PCP Unario». Se estudia si es o no indecidible el PCP Unario (PCPU), que es aquel cuyo alfabeto tiene un único símbolo: [Transparencias minimalistas de «Ejemplo de PCP Unario»]
• Mini-vídeo «Ejemplo de PCP Tonto».Se estudia si es o no indecidible el PCP Tonto (PCPT), que es aquel cuyas cadenas de la lista A tienen la misma longitud que las cadenas de la lista B:[Transparencias minimalistas de «Ejemplo de PCP Tonto»]
• Mini-vídeo «SAT, CSAT y 3SAT».Se muestran los problemas SAT, CSAT y 3SAT y se describe su intratabilidad: [Transparencias minimalistas de «SAT, CSAT y 3SAT»]
• Mini-vídeo «Reducción de CSAT a 3SAT».Se muestra el esquema de la demostración de la reducción de CSAT a 3SAT: [Transparencias minimalistas de «Reducción de CSAT a 3SAT»]
• Mini-vídeo «Ejemplo 1 del problema SAT».Se describe un ejemplo de expresión booleana y se estudia si es o no satisfacible: [Transparencias minimalistas de «Ejemplo 1 del problema SAT»]
• Mini-vídeo «Ejemplo 2 del problema SAT».Se describe otro ejemplo de expresión booleana y se estudia si es o no satisfacible: [Transparencias minimalistas de «Ejemplo 2 del problema SAT»]