¿Hay problemas que no se resuelven rápido?

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 ordenes.
Pero agrega ciudades una a una,
y la cantidad de ordenes a revisar
estalla en un parpadeo.
Usa el boton de abajo para agregar ciudades.

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

Cada vez que se agrega una ciudad,
los ordenes crecen multiplicandose.
Esto es el "crecimiento que explota"
que viste en la O grande.
Con apenas una docena de ciudades
los ordenes son tantos
que revisarlos uno por uno
se topa con un muro rapido.

Dificil de resolver, facil de comprobar

Pero aqui esta lo interesante.
Hallar la respuesta puede ser dificil,
pero si alguien te trae una,
comprobarla es rapido.
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 rapido. (hallar es dificil · revisar de un vistazo)

Dificil de hallar,
facil de comprobar.
Que esas dos se separen
es la marca de estos problemas.
La ruta del vendedor es igual.
Hallar la mas corta es dificil,
pero medir una ruta dada,
"cuanto mide este camino en total",
son solo unas cuantas sumas.

¿Existe una solucion rapida?

Aqui surge la gran pregunta.
"Si un problema es rapido de comprobar,
¿es rapido de resolver tambien?"
Quiza solo no hemos hallado
el metodo ingenioso aun.
O quiza de verdad
no existe solucion rapida alguna.
Haz clic en los dos lados de abajo.

Haz clic en los dos lados. (rapido de comprobar = rapido de resolver? · nadie lo sabe aun)

Asombrosamente, esta pregunta
aun no tiene respuesta conocida.
Matematicos y cientificos del mundo
llevan siglos lidiando con ella,
pero ni "existe una solucion rapida"
ni "no existe" se ha probado.
Este es el problema sin resolver
mas famoso de la informatica.
Asi que si alguien dice "es facil",
puedes dudar un poco.

Algunos problemas dificiles

Estos problemas no son uno solo.
La ruta mas corta por muchas ciudades,
elegir la carga mas valiosa
dentro de un limite 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 facil.
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 estan reunidos.
Curiosamente, si aunque sea uno
consigue una solucion rapida,
todos los demas se vuelven rapidos.
Estan tomados de la mano, en cierto modo.
Eso lo hace aun mas intrigante.
Resuelve uno y los resuelves todos.

Resumen

Juntemoslo en una linea.
Para algunos problemas, basta un pequeno
aumento de la entrada para que los casos exploten,
asi que no se conoce solucion rapida aun.
Pero hallar la respuesta es dificil
mientras comprobarla suele ser facil.
Entonces, si comprobar es rapido, ¿resolver lo es?
Eso nadie lo sabe todavia,
un gran misterio abierto.
Haz clic abajo para cerrar.

Haz clic en los puntos clave en orden para cerrar. (explosion → facil de comprobar → aun abierto)

No todo problema es igual de facil.
Algunos son de verdad duros.
Pero duro no es el final.
En la proxima historia
conoceremos formas ingeniosas que,
en vez de la respuesta perfecta,
hallan rapido
uno "suficientemente bueno".