En computación se crea una serie de problemas que se pueden resolver de una forma determinista, es decir, con una solución en la que existen garantías de validez, para ello se utilizan algoritmos de tipo polinomial que se desarrollan en tiempo polinomial. El ejemplo más sencillo sería hacer sumas, productos o la resolución de un gran número de ecuaciones. En la mayoría de los casos, mediante algoritmos adecuados, el tiempo de resolución se puede mantener dentro de intervalos aceptables. A todos los problemas que pueden ser tratados de esta forma se los considera problemas de tipo P. Por el contrario, se denominan problemas NP a aquellos para los que se puede encontrar un tipo de solución indeterminada, a base de probar soluciones que tal vez sean ciertas. Los tiempos de resolución para este tipo de problemas son muchísimos más rápidos que los empleados para los problemas de tipo P. Está claro que cualquier problema que admita una solución determinista en tiempo polinomial es también un problema al que se le puede aplicar una solución para una comprobación de tipo rápido. Dicho en otras palabras, todo problema de tipo P es de tipo NP.
¿Qué es un algoritmo?
Un algoritmo está constituido por una serie de instrucciones que no deben dejar lugar a dudas. Por ejemplo, para resolver una ecuación como x-2=8, el algoritmo de resolución diría algo así como:
1. Despejar x: x=8+2.
2. Hacer la operación correspondiente en el segundo miembro: 8+2=10.
3.Escribir la solución: x=10.
Este sería un problema tipo P que llevaría su correspondiente tiempo polinomial de resolución.
Se entiende que podríamos probar soluciones como x=3, x=-2... Y que el tiempo de computación sería mucho más rápido, ya que lo único que tiene que hacer el programa es colocar un valor en lugar de la x y comprobar si la solución es cierta.
La pregunta inversa consiste en lo siguiente. Si yo tengo un algoritmo de comprobación. ¿Puedo garantizar que existe un algoritmo polinomial que me permita resolver de manera determinista el problema?
Que es casi tanto como preguntarse si podemos estar seguros de que existirá algún tipo de algoritmo para buscar la solución en tiempo polinomial.
Este fue el problema que de manera independiente se plantearon en 1971 Stephen Cook y Leonid Levin. Si todo problema P es NP. ¿Existen problemas NP que no sean P? Este se considera el mayor reto que tiene planteada la computación actual y forma parte de uno de los Problemas del Milenio según los establece el Instituto Clay, de manera que quien los resuelva tiene la garantía de que dicha institución lo recompensará con la nada despreciable cifra de un millón de dólares.
