El problema de P versus NP se considera el problema abierto más importante en la ciencia de la computación. De hecho el Instituto Clay lo incluye entre los 7 “problemas del milenio”, que corresponden a los problemas matemáticos abiertos más importantes según ese instituto.
El premio por resolver alguno de estos problemas es de un millón de dólares. La descripción del Instituto Clay sobre el problema P versus NP es más o menos la siguiente:
Supongamos que estás organizando el alojamiento para un grupo de cuatrocientos estudiantes universitarios. El espacio es limitado y sólo cien de los estudiantes recibirán lugares en los dormitorios. Para complicar las cosas, el Decano te ha proporcionado una lista de parejas de estudiantes que presentan incompatibilidad entre sí, y pidió que ningún par de la lista aparezca en la distribución final.
Este es un ejemplo de lo que los científicos en computación llaman un problema NP, porque es fácil comprobar si una determinada lista de cien estudiantes propuestos es satisfactoria (es decir, ningún par tomado de lista aparece en la lista de incompatibilidades entregadas por el decano). Sin embargo la tarea de generar una lista desde el principio parece ser tan difícil, como completamente impracticable.
De hecho, el número total de maneras de elegir un centenar de estudiantes procedentes de los cuatrocientos solicitantes ¡es mayor que el número de átomos en el universo conocido! Así que ninguna civilización futura podría esperar construir un supercomputador capaz de resolver el problema por fuerza bruta, es decir, revisando cada posible combinación de 100 estudiantes.
Sin embargo, esta aparente dificultad sólo podría reflejar la falta de ingenio del programador. Uno de los problemas pendientes en ciencias de la computación es determinar si existen problemas cuya respuesta puede ser rápidamente verificada, pero que requieren un tiempo imposiblemente largo para resolver, por cualquier procedimiento directo. Problemas como el mencionado al principio parecen ser de este tipo, pero hasta ahora nadie ha logrado probar que algunos de ellos son realmente tan difíciles como parecen, es decir, que realmente no hay forma viable de generar una respuesta con la ayuda de un computador. Stephen Cook y Leonid Levin formularon en 1971, de forma independiente el problema de P versus NP.
La pregunta, en esencia, que propone el problema P versus NP es la siguiente:
Supongan que la solución a un problema puede ser verificada rápidamente con un computador. Entonces, ¿es posible que la solución en si misma pueda ser computada rápidamente?
Ustedes dirán, ¡estos son problemas de los matemáticos, o de los computólogos y si se resuelven no tiene ninguna importancia práctica!. Les sugiero que lo reconsideren, porque un problema matemático, más abstracto aún, propuesto hace unos 110 años atrás, llevó a la creación del computador, y generó todos los adelantos tecnológicos que disfrutamos en la actualidad gracias a la informática.
Interesante post, como un no-matemático me quedó relativamente claro de que va el problema.
Una duda con respecto al último párrafo, ¿cuál es ese problema aún más abstracto?
Es el segundo problema de Hilbert, que pide demostrar que la aritmética es consistente, es decir, que está libre de contradicciones. Kurt Godel demostró que no es así. Eso llevó plantear el Entscheidungsproblem, el problema de la detención, que también fue rebatidor por Turing.
En encontrar la respuesta a estos dos problemas tanto Turing, como Gõdel establecieron las bases formales de la computación, y los principios teóricos para construir los computadores digitales.
Una referencia:
http://www.lnds.net/blog/2010/06/la-maquina-de-turing-explicada-por-el-mismo-turing.html
Pero si tomamos la restricción como la solución inicial. (La peor de todas)
Realizamos la más pequeña modificación posible.
Comprobamos si esta solución es mejor a la anterior.
En caso de ser mejor, la adoptamos como la nueva solución, para reiniciar el ciclo de mejoras sucesivas.
Ese problema sería equivalente a saber si existe una partición de la restricción formada por pequeños test fácilmente verificables.
Saludos
Lo que propones es una heurística, pero no quita que el problema sigue siendo NP-Completo. La heurística tampoco te garantiza que encuentras todas las soluciones posibles.
P != NP , pero P es casi NP salvo algunos casos más difíciles (donde la heurísticas fallan, pero al menos son una solución aproximada bastante buena).
Es una corazonada sin ninguna base científica,
Saludos
Creo estar cerca de encontrar algo más allá de lo que buscaba.
http://picasaweb.google.com/tatadeluxe/ANN#slideshow/
Si la naturaleza utiliza algoritmos evolutivos para resolver problemas complejos, creo que eso podría ser un candidato a lo mejor que podríamos hacer.
Las 3 zonas (roja, amarilla, verde) me huelen a computación cuántica, pero no se nada de informática, ojalá algo de esto le haga sentido.
Saludos
[...] de las ciencias, donde vamos a ir resolviendo los problemas que nos plantea el universo, en ciclos de Integrar-Derivar con retroalimentación, donde tenderemos a aprender mucho y las computadoras serán un buen catalizador de ese [...]