Qué es P frente a NP

El número de casos explota

Supongamos que alguien tiene que visitar varias ciudades, cada una una sola vez, y quiere encontrar la ruta más corta.
Con tres ciudades, hay pocos órdenes posibles. Pero si añades ciudades una a una, el número de órdenes que hay que revisar se vuelve enorme en un abrir y cerrar de ojos.
Usa el botón de abajo para añadir ciudades.

Al añadir ciudades, el número de órdenes de visita explota. (ciudades +1 → los casos se multiplican)

Cada ciudad nueva multiplica el número de órdenes. Este es el «crecimiento explosivo» que vimos con la O grande.
Con apenas una docena de ciudades hay tantos órdenes que revisarlos uno a uno se atasca enseguida.

Difícil de resolver, fácil de comprobar

Pero hay algo interesante. Encontrar la respuesta puede ser difícil, pero si alguien te trae una, comprobar si es correcta es rápido.
Piensa en un sudoku. Rellenar todas las casillas da dolor de cabeza, pero revisar si un tablero completo cumple las reglas se hace con un vistazo.

Toca un candidato a respuesta y comprobarlo es rápido. (encontrar es difícil · revisar, un vistazo)

Difícil de encontrar, fácil de comprobar: que estas dos cosas vayan por separado es lo que caracteriza a estos problemas.
Con el problema del viajante pasa lo mismo. Encontrar la ruta más corta es difícil, pero si la pregunta es «¿hay una ruta cuya distancia total no pase de cierta cantidad?», basta con sumar las distancias de la ruta que alguien te da para confirmarlo.

¿Existe una solución rápida?

Aquí surge una gran pregunta: «Si un problema se comprueba rápido, ¿también se resuelve rápido?».
Quizá solo es que aún no hemos encontrado un método ingenioso, o quizá de verdad no existe una solución rápida.
Toca las dos posturas de abajo.

Toca las dos posturas. (¿comprobar rápido = resolver rápido? · nadie lo sabe aún)

Sorprendentemente, nadie conoce todavía la respuesta a esta pregunta. Matemáticos y científicos de todo el mundo le han dedicado mucho tiempo, pero nadie ha logrado demostrar ni que «hay una solución rápida» ni que «no la hay».
Es el problema sin resolver más famoso de la informática. Así que, si alguien te dice que es fácil, es razonable dudar un poco.

Problemas difíciles

Este tipo de problema no es único. Está la ruta más corta por muchas ciudades, la mochila con los objetos más valiosos dentro de un límite de peso y el coloreado de un mapa para que los países vecinos no compartan color.
Por fuera parecen distintos, pero por dentro se parecen: el número de casos explota y comprobar es fácil.
Cambia entre los ejemplos de abajo.

Toca un ejemplo para cambiarlo. (viajante · mochila · coloreado de grafos, todos con el mismo tipo de dificultad)

Se han reunido miles de problemas parecidos. Lo asombroso es que, si alguien encuentra una forma rápida de resolver uno solo de ellos, todos los demás también se pueden resolver rápido.
En cierto modo van de la mano, y eso lo hace aún más intrigante: resuelves uno y los has resuelto todos.

Resumen

En una línea: en algunos problemas, el número de casos explota en cuanto la entrada crece un poco, así que todavía no se conoce una solución rápida.
Aun así, aunque encontrar la respuesta sea difícil, comprobarla suele ser fácil. Entonces, si comprobar es rápido, ¿resolver también lo es? Es un gran enigma que nadie ha resuelto todavía.
Toca los puntos de abajo en orden para resumir.

Toca los puntos clave en orden para resumir. (explosión → comprobar es fácil → aún sin resolver)

No todos los problemas son igual de fáciles; algunos son realmente duros.
Pero ser duro no significa el final. En la próxima lección conoceremos métodos ingeniosos que renuncian a la respuesta perfecta y, a cambio, encuentran rápido una respuesta «suficientemente buena».