cómo Qué es P frente a NP

Los casos explotan

Una persona debe visitar
varias ciudades, cada una una vez.
Queremos la ruta más corta.
Con tres ciudades
hay solo unos pocos órdenes.
Pero agrega ciudades una a una,
y la cantidad de órdenes a revisar
estalla en un parpadeo.
Usa el botón de abajo para agregar ciudades.

Agrega una ciudad y la cantidad de órdenes explota. (ciudad +1 → los casos se multiplican)

Cada vez que se agrega una ciudad,
los órdenes crecen multiplicándose.
Esto es el "crecimiento que explota"
que viste en la O grande.
Con apenas una docena de ciudades
los órdenes son tantos
que revisarlos uno por uno
se topa con un muro rápido.

Difícil de resolver, fácil de comprobar

Pero aquí está lo interesante.
Hallar la respuesta puede ser difícil,
pero si alguien te trae una,
comprobarla es rápido.
Piensa en el Sudoku.
Llenar cada casilla es un dolor de cabeza.
Pero tomar un tablero ya lleno
y revisarlo contra las reglas
es solo un vistazo con los ojos.

Haz clic en una respuesta candidata y comprobar es rápido. (hallar es difícil · revisar de un vistazo)

Difícil de hallar,
fácil de comprobar.
Que esas dos se separen
es la marca de estos problemas.
La ruta del vendedor es igual.
Hallar la más corta es difícil,
pero medir una ruta dada,
"cuánto mide este camino en total",
son solo unas cuantas sumas.

¿Existe una solución rápida?

Aquí surge la gran pregunta.
"Si un problema es rápido de comprobar,
¿es rápido de resolver también?"
Quizá solo no hemos hallado
el método ingenioso aún.
O quizá de verdad
no existe solución rápida alguna.
Haz clic en los dos lados de abajo.

Haz clic en los dos lados. (rápido de comprobar = rápido de resolver? · nadie lo sabe aún)

Asombrosamente, esta pregunta
aún no tiene respuesta conocida.
Matemáticos y científicos del mundo
llevan siglos lidiando con ella,
pero ni "existe una solución rápida"
ni "no existe" se ha probado.
Este es el problema sin resolver
más famoso de la informática.
Así que si alguien dice "es fácil",
puedes dudar un poco.

Algunos problemas difíciles

Estos problemas no son uno solo.
La ruta más corta por muchas ciudades,
elegir la carga más valiosa
dentro de un límite de peso, la mochila,
colorear un mapa para que los vecinos
nunca compartan color.
En la superficie lucen distintos,
pero en el fondo se parecen.
Los casos explotan,
y comprobar es fácil.
Cambia de ejemplo abajo.

Haz clic para cambiar de ejemplo. (vendedor · mochila · coloreo de mapa — el mismo tipo de dificultad)

Cientos de estos problemas
parecidos están reunidos.
Curiosamente, si aunque sea uno
consigue una solución rápida,
todos los demás se vuelven rápidos.
Están tomados de la mano, en cierto modo.
Eso lo hace aun más intrigante.
Resuelve uno y los resuelves todos.

Resumen

Juntémoslo en una línea.
Para algunos problemas, basta un pequeño
aumento de la entrada para que los casos exploten,
así que no se conoce solución rápida aún.
Pero hallar la respuesta es difícil
mientras comprobarla suele ser fácil.
Entonces, si comprobar es rápido, ¿resolver lo es?
Eso nadie lo sabe todavía,
un gran misterio abierto.
Haz clic abajo para cerrar.

Haz clic en los puntos clave en orden para cerrar. (explosión → fácil de comprobar → aún abierto)

No todo problema es igual de fácil.
Algunos son de verdad duros.
Pero duro no es el final.
En la próxima historia
conoceremos formas ingeniosas que,
en vez de la respuesta perfecta,
hallan rápido
uno "suficientemente bueno".