el 24 de mayo de 2000, Clay Mathematics Institute presentó siete problemas matemáticos, por los cuales, la solución para cualquiera de los problemas ganará una recompensa de US reward 1,000,000 para el solucionador. Conocidos como los problemas del milenio, hasta ahora, solo uno de los siete problemas se ha resuelto hasta la fecha.
Si quieres ganar un millón de dólares, intenta resolver uno de esta lista. Estos son los problemas enumerados para una recompensa de premio de un millón de dólares.,
- Yang–Mills and Mass Gap
- hipótesis de Riemann
- problema P vs NP
- ecuación de Navier–Stokes
- conjetura de Hodge
- conjetura de Poincaré
- conjetura de Birch y Swinnerton-Dyer
bien, seamos realistas aquí, estos problemas están aquí por una razón. Lo adivinaste bien, estos problemas son difíciles de resolver. De hecho, son profundas y realmente difíciles, no solo para resolverlas, sino incluso para entender la declaración del problema. La mayoría de los problemas enumerados necesitarán un sólido conocimiento y análisis del tema, incluso para comprender la pregunta.,
la conjetura de Poincaré es el único problema que se resuelve entre estas siete preguntas. Este problema proviene del dominio de la topología, que trata sobre cómo los objetos encajan entre sí y su forma en el espacio. Este problema estaba específicamente relacionado con esferas.
en 1904 El matemático francés Henri Poincaré preguntó si la esfera tridimensional se caracteriza como la única variedad de tres simplemente conectadas. Esta pregunta, la conjetura de Poincaré, fue un caso especial de la conjetura de geometrización de Thurston., La prueba de Perelman nos dice que cada tres variedades se construye a partir de un conjunto de piezas estándar, cada una con una de ocho geometrías bien entendidas.
Refer: https://www.claymath.org/millennium-problems
Complicated stuff uhmmm! Vamos a discutir un poco más de esto antes de pasar a P versus NP.
Henri Poincaré, planteó el problema en 1904, que en general establece que, si tienes un objeto sin agujeros y su tamaño es bastante pequeño y finito, entonces es una esfera (o puede convertirse en una esfera). Esto no es solo para 3 dimensiones, sino para todas las dimensiones.,
pero la declaración no fue probada para la cuarta dimensión, hasta que Grigori Perelman llegó con la solución en 2003, basada en el trabajo de Richard Hamilton.
si está interesado, aquí está cómo se ve una solución de un millón de dólares: https://arxiv.org/abs/math/0211159
Grigori Perelman fue galardonado con un millón de dólares y la Medalla fields, ambas rechazadas.
¿Qué decir? A algunos nos gusta resolver problemas, solo por la diversión de resolverlos.
la Felicidad es disfrutar el proceso!,
P versus NP es el problema más reciente que se listó en la lista de problemas del Milenio. Este problema se planteó en 1971.
la declaración precisa del problema P versus NP fue introducida en 1971 por Stephen Cook en su artículo seminal «the complexity of theorem proving procedures».
para entender correctamente el problema P versus NP, el conocimiento básico de la complejidad computacional es una necesidad. De hecho P vs NP es el problema más esperado para la solución en Ciencias de la computación., Por lo tanto, un buen agarre de cómo este problema afecta el panorama informático nos ayudará a digerir este problema.
Si eres nuevo en el tema de la complejidad computacional o la complejidad en general, te animaré a echar un vistazo a mi historia anterior sobre «¿qué es la complejidad computacional?»
La mayoría de los problemas en el espacio computacional se pueden reducir a un problema de decisión. Eso significa problemas donde la respuesta es sí o NO.
así que volvamos a la pregunta de qué es P? ¿y qué es NP?,
tanto P como NP pueden considerarse como un conjunto de problemas que se agrupan en función de lo difícil que es resolver y evaluar la solución. El término difícil es particularmente importante en este contexto, que básicamente significa que cuán computacionalmente intensivo es un problema para resolver y verificar la solución.
Por ejemplo, considere el problema de la multiplicación. Este es un problema relativamente fácil de resolver. No solo que este problema es fácil de resolver, esto también se puede verificar con la misma facilidad simplemente multiplicando los números., Básicamente, cualquier problema que se puede resolver en tiempo polinómico y cuyo resultado se puede verificar en tiempo polinómico, está bajo el conjunto de complejidad de P.
P (polynomial time) contiene todos los problemas de decisión que se pueden resolver por una máquina de Turing determinista utilizando una cantidad polinómica de tiempo de cálculo, o tiempo polinómico.
hay este otro conjunto de problemas que se pueden verificar en tiempo polinómico pero, para resolver este problema tomará más que tiempo polinómico. Por ejemplo, tomemos el Sudoku por ejemplo., Dado que tenemos una solución para cualquier juego, podemos verificarlo fácilmente. Esto significa que podemos hacer la parte de verificación en tiempo polinómico. Pero para resolver el rompecabezas, necesitamos más tiempo. También a medida que aumenta el número de cuadrículas, la complejidad de encontrar una solución aumenta exponencialmente.
NP (nondeterministic polynomial time) es una clase de complejidad utilizada para clasificar problemas de decisión. NP es el conjunto de problemas de decisión para los cuales las instancias problemáticas, donde la respuesta es «sí», tienen pruebas verificables en tiempo polinómico., (sólo pueden ser exponencialmente grande, no más grande)
punto Interesante a tener en cuenta es que cada problema que está en P es también una parte de la NP. Pero esto podría o no ser viceversa. Aquí es donde la mentalidad de investigación entra en juego. Por lo tanto, la solución para los problemas de NP es lenta, pero se pueden verificar rápidamente. ¿Podemos mejorar la velocidad de la solución?
veamos el problema de primalidad. Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo.,
dado el número natural n, es N primo?
Este problema se consideró un problema en el subconjunto de NP hasta que la prueba de primalidad de AKS demostró que este problema está bajo P.,
la prueba de primalidad de AKS (también conocida como prueba de primalidad de Agrawal–Kayal–Saxena y prueba de AKS ciclotómica) es un algoritmo determinista de prueba de primalidad creado y publicado por Manindra Agrawal, Neeraj Kayal y Nitin Saxena, científicos informáticos del Instituto Indio de tecnología Kanpur, el 6 de agosto de 2002, en un artículo titulado «PRIMES is in P»
entonces, ¿existe la posibilidad de que todos los problemas en NP se puedan resolver en complejidad P?, ¿O hay un conjunto de problemas que siempre serán difíciles de encontrar solución para hacer que P y NP siempre permanezcan separados? La respuesta es desconocida. De hecho, ese es el problema del millón de dólares.
si es fácil comprobar que una solución a un problema es correcta, ¿también es fácil resolver el problema?
típico de los problemas de NP es el problema de la ruta hamiltoniana: dadas N ciudades para visitar, ¿cómo se puede hacer esto sin visitar una ciudad dos veces? Si me da una solución, puedo comprobar fácilmente que es correcta. Pero no puedo encontrar tan fácilmente una solución.,
Refer: https://www.claymath.org/millennium-problems/p-vs-NP-problem
algunos problemas en NP se pueden agrupar como NP completo. Este es un grupo de problemas donde si se encuentra una solución rápida a cualquiera de uno de los problemas podemos resolver un grupo de problemas en el mismo conjunto de complejidad con facilidad.
un problema es NP-completo cuando puede ser resuelto por una clase restringida de Algoritmos de búsqueda de fuerza bruta y puede ser utilizado para simular cualquier otro problema con un algoritmo similar.,
la completitud NP es particularmente importante en la discusión P versus NP como solución en tiempo P, porque un problema en el conjunto completo NP demuestra que todo el conjunto de complejidad colapsará. Lo que significa que NP-Complete = NP = P
un problema NP-complete estará en NP y estará en NP-Hard lo que significa que este problema es al menos tan difícil como cualquier problema en NP, como se ilustra a continuación.,
Un problema es NP-es duro si un algoritmo para la solución puede ser traducido a uno para resolver cualquier NP-problema (no deterministas polinomio tiempo) problema. Por lo tanto, NP-hard significa «al menos tan duro como cualquier problema NP», aunque podría, de hecho, ser más difícil.
hay problemas fuera de NP que son difíciles de hacer una solución al mismo tiempo difícil comprobar la solución también, por ejemplo, considerar Ajedrez., Dada cualquier posición en un tablero es difícil encontrar el mejor siguiente movimiento también es difícil verificar que el siguiente movimiento sea preciso o no. Este problema está en EXP (Exponential time complexity) y tal vez fuera de NP.
La mayoría de los investigadores en el campo de la teoría de la complejidad computacional cree que P no es igual a NP. Evento aunque hay muchos problemas interesantes en NP que afecta a nuestra vida de hoy en día como problemas de optimización. Una solución a un problema completo de NP como el plegamiento de proteínas significa que estaremos mucho más cerca de encontrar la cura para el cáncer., Además, si P=NP, entonces podríamos encontrar que la criptografía de Clave Pública está rota, ya que depende de la factorización de enteros, que es un problema en NP y dependemos de esta dureza para la solución de la mayor parte de nuestra criptografía. Por lo tanto, las implicaciones de probar N=NP es mixto.
hubo mucha investigación para probar P = NP o viceversa. Pero este problema en sí parece ser NP-duro (solo siendo sarcástico aquí) ya que no hay resultados concluyentes hasta ahora. Pero el mundo será un lugar mucho más interesante si alguien puede probar que P = NP., Pero a partir de ahora, la mayoría de la gente bien educada del campo piensa lo contrario.
en su blog, famous researcher computational complexity theory, Scott Aaronson afirma que,
Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que normalmente Suponemos que es. No habría ningún valor especial en los «saltos creativos», ninguna brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentra., Todo el que pudiera apreciar una sinfonía sería Mozart; todo el que pudiera seguir un argumento paso a paso sería Gauss; todo el que pudiera reconocer una buena estrategia de inversión sería Warren Buffett.
Gracias por su tiempo.
Editado por Ashok Jeevan
Deja una respuesta