GUÍA 28-09-26 Teoría de la Computación

NE111 · lunes 28/09/2026 · 16:00-17:15 · Sesión 14

Problemas P y NP

LA CLASE P

Problemas de decisión resolubles por una máquina de Turing determinista en tiempo O(nᵏ) para algún k fijo. Se identifica informalmente con lo tratable.

• Ordenar, búsqueda binaria, caminos mínimos, flujo máximo, primalidad.

LA CLASE NP

Problemas resolubles por una máquina de Turing no determinista en tiempo polinomial. La caracterización útil es la equivalente: son los problemas cuya solución, si alguien la propone, puede verificarse en tiempo polinomial.

• SAT — ¿es satisfacible esta fórmula booleana? Verificar una asignación propuesta es trivial.
• Ciclo hamiltoniano — verificar un ciclo propuesto es fácil; encontrarlo no.
• Coloreo de grafos, mochila, agente viajero en versión de decisión.

EL CERTIFICADO

La forma práctica de probar que un problema está en NP es exhibir el certificado: qué información bastaría para convencer a alguien de que la respuesta es sí, y comprobar que verificarla toma tiempo polinomial. Para el ciclo hamiltoniano el certificado es la lista de vértices en orden.

P ⊆ NP

Si se puede resolver rápido, se puede verificar rápido: basta resolverlo e ignorar el certificado. La inclusión es evidente. Lo que nadie sabe es si es estricta.

EL PROBLEMA P CONTRA NP

¿Todo problema verificable rápido es resoluble rápido? Es el problema abierto más importante de la computación y uno de los siete problemas del milenio, con un premio de un millón de dólares. La opinión mayoritaria es que P ≠ NP, pero no hay demostración en ninguna dirección.

POR QUÉ IMPORTA FUERA DE LA TEORÍA

Si P = NP, la criptografía de clave pública colapsa, porque romperla se vuelve tan fácil como usarla. Si P ≠ NP, hay problemas que jamás tendrán algoritmo eficiente y conviene invertir en aproximaciones y heurísticas en lugar de perseguir el óptimo.

RELACIÓN CON LO ANTERIOR

Nota la diferencia con el bloque de computabilidad. Los problemas NP sí son decidibles: existe algoritmo, solo que exponencial. La indecidibilidad es un muro absoluto; la intratabilidad es un muro práctico.

EJERCICIO

Clasificar diez problemas en P o NP y dar el certificado verificable de cada uno de los de NP.