¿Por qué no se incluye la factorización prima en los problemas del Premio del Milenio?

Answer 1

Los problemas del Premio del Milenio son siete. Hay miles de problemas abiertos en matemáticas. Ergo, muchos problemas tuvieron que quedar fuera, incluidos algunos que son profundos, significativos e interesantes.

El problema de la factorización de enteros es un problema de complejidad computacional: encuentre un algoritmo eficiente para factorizar enteros (probablemente imposible), o pruebe que no existe ninguno. Ya existe un Problema del Premio del Milenio sobre la complejidad computacional, y es increíblemente más profundo y de mayor alcance: P vs NP.

La inclusión de otro problema de complejidad en la parte superior de P vs NP habría sido muy sesgada. Los problemas intentan abarcar diversos dominios matemáticos y, por supuesto, con solo siete problemas, se van a omitir campos completos. Elegir dos problemas de un dominio no tiene sentido, e incluir Factorización entera en lugar de P vs NP tiene aún menos sentido.

Answer 2

En mi humilde opinión, mi opinión es que los siete problemas del Premio del Milenio han sido cuidadosamente seleccionados después de elaboradas deliberaciones con los expertos de campo. De los siete, uno está resuelto a partir de ahora (Conjetura de Poincare de Grigori Perelman, quien rechazó el premio de USD $ 1 millón en 2010). Millennium Prize Problems es mi fuente de información no autorizada, pero también es un hecho bien conocido.

Se espera que la solución a cualquiera de los problemas fomente sustancialmente el estado del conocimiento en un campo matemático y posiblemente en muchos otros campos relacionados o no relacionados.

Ya se sabe que el problema de Factorización Prime (PF) está en la clase de complejidad NP (Factorización Prime), por lo que podemos relacionarlo con el problema P vs NP. Eso significa que tiene un certificado que puede verificarse en tiempo polinómico. Resolver PF puede proporcionar una idea del problema P vs NP. Al resolver PF, si todos los aspectos del problema y la solución se pueden explicar, entonces puede contar como un progreso sólido en uno de los problemas del Premio del Milenio. Una solución aquí significa una solución óptima , que muestra que ninguna otra solución puede ser mejor que la propuesta, con respecto a las medidas de complejidad bien conocidas.

Entonces, en cierto modo, el Comité del Milenio no destacó los problemas de Factorización Prime o k-SAT o XOR-SAT para el Premio, sino que está pidiendo resolver la clase completa de estos problemas conocidos en NP de la manera más eficiente posible , en el sentido de complejidad de la palabra. Si la solución “óptima” de alguien cae en P, entonces el problema NP vs P se resuelve a favor de NP = P. Pero esto parece poco probable y ahora es bastante evidente que obtener una solución “óptima” de PF tampoco es un juego justo, ya que esto proporcionará una herramienta para la separación de la clase de problemas P vs NP.

Agregar PF al Premio Millenium habría sido redundante.

EDITAR: Alon Amit ha señalado que PF está en NP pero no se sabe que NP está completo. Esto significa que aunque PF está en la misma casa con k-SAT, posiblemente no esté en la misma habitación con él. Sin embargo, una solución a PF puede proporcionar una idea de la separación de P vs NP.