P vs NP

El tiempo de ejecución de un algoritmo computacional se define como la cantidad de operaciones elementales que el algoritmo realiza para entregar la respuesta, y se expresa generalmente en función del tamaño de la entrada. Por ejemplo, el problema del ordenamiento recibe como entrada una lista de n números, la respuesta es la lista ordenada de menor a mayor, y los algoritmos más sencillos de ordenamiento tienen tiempo de ejecución del orden de n^2. Este último hecho hace que este problema pertenezca a la clase de problemas P, que son todos aquellos problemas computacionales que tienen algún algoritmo de solución de tiempo de ejecución acotado superiormente por un polinomio en n. En cambio, existe la clase de los problemas NP a los que solo nos importa verificar la validez de una solución en tiempo polinomial. Por ejemplo, el problema de dada una red de n nodos donde se conoce el costo de desplazamiento entre cada pareja de nodos, y cierto costo C, decidir si existe una ruta que pase por todos los nodos sin repeticiones y con costo total menor que C, se le conocen únicamente algoritmos cuyos tiempos de ejecución son esencialmente del orden de n!, que no es polinomial. Sin embargo, validar que cierta ruta sea en efecto una respuesta al problema lo podemos lograr de manera sencilla en tiempo polinomial. 

De lo anterior surge la siguiente implicación: Todo problema P también es NP, porque si podemos generar la solución en tiempo polinomial también podemos hacer la verificación en dicho tiempo. 

La gran pregunta abierta, la cual es uno de los 7 problemas matemáticos del milenio, es: ¿Será P distinto a NP, o será P igual a NP? Dicho de otra forma, ¿existirán problemas en la clase NP que nunca podrán ser resueltos en tiempo polinomial por ningún algoritmo, o todos los problemas NP podrán ser resueltos en dicho tiempo?