Bueno, hay una gran importancia en poder resolver un problema en el tiempo polinómico por encima del tiempo exponencial. Se podría decir, bueno, ¿no es f (x) = x ^ 100000 una función polinómica, y eso no requeriría un tiempo de ejecución muy largo en comparación con la función exponencial 2 ^ x? Sí, eso es cierto, pero si un problema se puede resolver en tiempo polinómico, el exponente unido a la constante generalmente se puede reducir. Es decir, x ^ 100000 puede reducirse a x ^ 10 o x ^ 2 a través de algoritmos más eficientes. Sin embargo, esto no siempre se puede decir que sea cierto para las funciones exponenciales.
Seguramente sabe que la dificultad de resolver problemas de NP tiene que ver con la forma en que el tiempo necesario para una solución escala con complejidad. Por ejemplo, el problema del vendedor ambulante es trivial de resolver con 3 ciudades. Sin embargo, pruebe 100 ciudades y no tendrá suerte. La dificultad del problema aumenta muy rápidamente a medida que la complejidad aumenta. La incapacidad para reducir la función de complejidad temporal (que generalmente se puede hacer con funciones polinómicas) es la característica clave de un problema de NP y es por eso que es muy difícil de resolver. Probar P vs NP puede no ser tan importante, pero idear un algoritmo eficiente para resolver problemas de NP en tiempo polinómico será revolucionario, ya que muchos problemas importantes son NP. Estos incluyen, entre otros, la predicción del plegamiento de proteínas, el diseño del chip VLSI, los problemas de optimización y el pronóstico de los mercados económicos. Si uno desarrollara un algoritmo eficiente para resolver alguno o todos estos problemas de NP en tiempo polinómico, uno revolucionaría las industrias de salud, informática y financiera. ¡Elige cuál o todos! 🙂
Además, ¿qué es el universo excepto los algoritmos? Los humanos han diseñado sistemas matemáticos para describir los comportamientos de electrones, átomos, moléculas, cuerpos termodinámicos, etc., que son esencialmente algoritmos que describen cómo deben comportarse dichos objetos bajo ciertas condiciones. Si la predicción precisa del plegamiento de proteínas es un problema NP difícil, entonces de alguna manera los billones de células en nuestros cuerpos pueden realizar constantemente estos cálculos enormemente difíciles (o quién sabe, podrían no ser).
Si P! = NP, nadie se sorprendería. Sin embargo, si P = NP, eso tendría algunas implicaciones filosóficas serias para la naturaleza de nuestro universo. Independientemente de las implicaciones filosóficas, los algoritmos eficientes para resolver problemas de NP incluso en alta complejidad tendrían enormes aplicaciones prácticas en casi cualquier industria que se te ocurra.
