P versus NP

Definición

Pregunta abierta que busca determinar si todo problema de decisión cuya solución puede verificarse en tiempo polinomial también puede resolverse en tiempo polinomial.

Formulación

$$\mathrm{P}\stackrel{?}{=}\mathrm{NP}$$

• $\mathrm{P}$: problemas de decisión resolubles en tiempo polinomial por un algoritmo determinista.
• $\mathrm{NP}$: problemas de decisión cuyas soluciones afirmativas poseen certificados verificables en tiempo polinomial.

Ejemplo mínimo

En satisfacibilidad de circuitos, una asignación que hace verdadera la salida puede verificarse rápidamente, pero no se conoce un algoritmo polinomial que siempre encuentre tal asignación o determine que no existe.

Contraejemplo o límites

$\mathrm{NP}$ no significa “no polinomial”. Se sabe que $\mathrm{P}\subseteq \mathrm{NP}$; lo desconocido es si la inclusión es estricta.

Relaciones

• Requiere conocer: Tiempo polinomial.
• Caso representativo: Satisfacibilidad de circuitos.
• Pertenece a: teoría de la complejidad computacional.

Procedencia

• Clase: Introducción al curso
• Fuente: presentación introductoria, diapositiva 19.
• Estado: problema abierto; la presentación lo describe como la “pregunta del millón”.