Es uno de los enigmas del milenio conocido como de P vs NP (en.wikipedia.org/wiki/Millennium_Prize_Problems). Y es uno de los problemas de lógica computacional que no se han podido resolver.
Los problemas de tipo P son aquellos que tienen una solución de coste polinómico (o sea, que a más grande el problema, el tiempo que se necesita crece linealmente).
Los problemas de tipo NP son problemas que se caracterizan por que, dada una posible solución, tardan un tiempo polinómico (P) en saber si la solución es válida. Todos los problemas NP tienen un número exponencial de soluciones en función del tamaño del problema (o sea, si el problema es el doble de grande, el número de soluciones se eleva al cuadrado). Así, la solución general de un problema NP es generar todas las posibles soluciones y testar cada una de ellas (cada test es de coste P) hasta dar con una (si necesitamos una) o probar todas las combinaciones para hallar todas las soluciones. Como hay un número exponencial de soluciones, ejecutamos un algoritmo de coste P un número exponencial de veces, lo que nos lleva a un coste exponencial.
Básicamente, si se resolviera y se demostrara que P = NP, se habría encontrado un algoritmo que resuelve de manera muy eficiente problemas que, hasta ahora, requieren de años de computación para encontrar solución (o sea, que resuelva los problemas de NP con coste P). La otra posibilidad es que se resuelva y se demostrara que P != NP, en cuyo caso se estaría seguro de que no existen soluciones más eficientes para los problemas NP que las que ya se conocen.
Finalmente, conviene comentar que todos los problemas NP están relacionados entre ellos. O sea, los ejemplos de problemas NP no son sino diferentes maneras de plantear el mismo problema computacional. Eso quiere decir que, si se encontrara una solución de coste P para uno de ellos (eg: el problema de las damas en un tablero N x N casillas), esta solución es fácilmente transformable para resolver cualquiera de los otros ejemplos de NP.
Los problemas de tipo P son aquellos que tienen una solución de coste polinómico (o sea, que a más grande el problema, el tiempo que se necesita crece linealmente).
Los problemas de tipo NP son problemas que se caracterizan por que, dada una posible solución, tardan un tiempo polinómico (P) en saber si la solución es válida. Todos los problemas NP tienen un número exponencial de soluciones en función del tamaño del problema (o sea, si el problema es el doble de grande, el número de soluciones se eleva al cuadrado). Así, la solución general de un problema NP es generar todas las posibles soluciones y testar cada una de ellas (cada test es de coste P) hasta dar con una (si necesitamos una) o probar todas las combinaciones para hallar todas las soluciones. Como hay un número exponencial de soluciones, ejecutamos un algoritmo de coste P un número exponencial de veces, lo que nos lleva a un coste exponencial.
Básicamente, si se resolviera y se demostrara que P = NP, se habría encontrado un algoritmo que resuelve de manera muy eficiente problemas que, hasta ahora, requieren de años de computación para encontrar solución (o sea, que resuelva los problemas de NP con coste P). La otra posibilidad es que se resuelva y se demostrara que P != NP, en cuyo caso se estaría seguro de que no existen soluciones más eficientes para los problemas NP que las que ya se conocen.
Finalmente, conviene comentar que todos los problemas NP están relacionados entre ellos. O sea, los ejemplos de problemas NP no son sino diferentes maneras de plantear el mismo problema computacional. Eso quiere decir que, si se encontrara una solución de coste P para uno de ellos (eg: el problema de las damas en un tablero N x N casillas), esta solución es fácilmente transformable para resolver cualquiera de los otros ejemplos de NP.
Para saber más sobre el tema de P y NP:
es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP