noticias y última hora

Los problemas del millón de doláres

En las matemáticas no todos los problemas están resueltos, como hemos comentado en Gaussianos más de una vez. De hecho hay unos problemas ya hablé hace tiempo sobre los problemas de Hilbert, 23 problemas que propusó David Hilbert en el congreso internacional de matemáticos de 1900 para ser resueltos en el siglo XX y ser influyentes en las matemáticas de ese siglo.

Si bien de esos 23 problemas, se resolvieron la mayoría en ese siglo, todavía quedan otros problemas que han ido surgiendo y que por su complejidad siguen sin ser resueltos, a estos problemas se les llamó los problemas del milenio.

Estos problemas en principio eran ocho, pero Andrew Wiles se adelantó resolviendo antes del fin del siglo XX el último teorema de fermat. Así los problemas del milenio al final sólo fueron siete, y se hicieron bastante famosos cuando el instituto Clay anunció que recompensaría con un millón de doláres por problema resuelto.

Los siete problemas del milenio son:

  1. P vs NP
  2. La conjetura de Hodge
  3. La conjetura de Poincaré: Este problema lo explicamos en Gaussianos. (Explicación)
  4. La hipótesis de Riemann
  5. Existencia de Yang-Mills y del salto de masa
  6. Las ecuaciones de Navier-Stokes: Parece ser que hay grandes avances. (Información)
  7. La conjetura de Birch y Swinnerton-Dyer

Hace poco, este año, se resolvió uno de ellos, concretamente la conjetura de Poincaré. Este problema fue resuelto por Grigori Perelman, además como consecuencia de esto se le otorgó la medalla fields y el millón de doláres correspondiente, pero Perelman se negó a aceptarlos.

Quizá más adelante me atreva (o nos atrevamos) a explicar un poco cada uno de los seis problemas que quedan por explicar.

(Más información en Wikipedia)


Posts aleatorios

Autor: Fran  |  Publicado el 12 de December de 2006
Categorías: Curiosidades, Historia, Matemáticas  |  Imprime este post Imprime este post

Sin comentarios

  1. mimetist | 12 de December de 2006 | 17:06

    Son las 6 puntitas del iceberg de las matemáticas en nuestros días…

    Gussianos… ¿por cuál empezamos?

  2. neok | 12 de December de 2006 | 17:24

    Pues si te digo la verdad, a mí la que me parece que más pasta puede dar, además del millón de doláres, es la hipótesis de Riemann, ya que te cargarías (casi) toda la seguridad informática de estos tiempos, las demás no sé muy bien cuánto dinero pueden dar. Esto es un punto de vista en base al dinero, puede haber otros puntos de vista. ;)

  3. Jaume | 12 de December de 2006 | 20:01

    No estoy seguro de que la seguridad de nuestras comunicaciones se sostenga por la posible certeza de la hipótesis de Riemann ;)

    En realidad si fuera cierta podrias usarla con seguridad para saber si un número es primo o no de forma más eficiente. Aún así si quieres puedes usarla igualmente :P

    En todo caso el conocer la primalidad de un determinado numero no compromete ningún sistema criptografico.

    Hace tiempo salió en kriptópolis un divertido artículo que analizando aquella serie…i que expresa bastante bién cosas como esta:
    http://www.kriptopolis.org/numb3rs-una-de-cal-y-otra-de-arena

    Saludos y animo con vuestro trabajo.

    Jaume

  4. mimetist | 12 de December de 2006 | 21:52

    Como dice Jaume, comprobar la Hipótesis de Riemann no compromete la seguridad de ningún sistema puesto que ya se puede usar (y se usa) como si fuese cierta… pero en matemáticas no estaremos satisfechos hasta que alguien la compruebe para disipar toda duda.

    Lo que sí se cargaría cualquier sistema de seguridad informático es un método “rápido” de factorización.

    Creo que todos pueden dar pasta por igual. Resolver cualquiera de ellos te asegura fama en la comunidad científica y trabajo en cualquier universidad…

  5. Wolfaint | 12 de December de 2006 | 22:15

    Yo le voy mas en cuanto a dinero al P vs NP… si se pudiera resolver, se crearia la makina de truman(kreo ke asi se llama) y todas las pc a la basura por ke llego lo mejor encunanto a Informacion.

    CLaro resolverlo esta mas dificil ke los otros 5 juntos.. xD

    mejor empecemos por el del TSP

  6. Jordi | 12 de December de 2006 | 23:54

    Wolfaint creo que se refería a la máquina de Turing. El tema es que la máquina de Turing ya está hecha, nuestros ordenadores actuales son equivalentes a la máquina de Turing. El tipo de máquina nueva que se cargaría la seguridad informática sería el ordenador cuántico, puesto que éste utilizaría un modelo de funcionamiento distinto a la máquina de Turing, y para el cual (aunque no exista físicamente la máquina aún) ya se han hecho los algoritmos que hacen que ahí P = NP.

    Así que el problema que realmente puede ser peligroso para la seguridad informática es el de P vs NP. P son las cosas que se puede calcular en un tiempo polinómico. NP son las cosas que se puede calcular en un tiempo exponencial, aunque en una máquina de Turing No Determinista (lo que sería un ordenador cuántico) podrían calcularse en tiempo polinómico. De ahí viene la N de las siglas NP, de Non-Deterministic.

    Toda nuestra seguridad se basa en que si tú tienes la clave, puedes desencriptar el texto codificado con un algoritmo P. En cambio, si no la sabes, ver todas las posibilidades sería NP, exponencial, y por lo tanto no es seguro que pudieras desencriptar antes del fin del universo un mail de Bin Laden pidiendo abono para un huerto de patatas.

    Probablemente P sea distinto de NP y desde este punto de vista podamos estar más tranquilos, pero es muy jodido de demostrar. La demostración de que P es distinto de EXP (las cosas que son exponenciales de calcular incluso para una máquina de Turing no determinista) es realmente un conejo sacado de la chistera. Y no se ha podido demostrar la relación de NP ni con P ni con EXP.

    Espero haber sido útil…

  7. Wolfaint | 13 de December de 2006 | 00:50

    Tengo ke diferir, y si es la makina de turing(mi memoria regresa y se va )

    La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo.

    http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

    Yo no creo ke ya este hecha, si no ke diablos estamos haciendo en estas pc…

  8. Jordi | 13 de December de 2006 | 01:26

    Bueno, entonces no estamos diferiendo en nada. La máquina de Turing es, efectivamente, un modelo. Y nuestras PC’s son equivalentes computacionalmente a este modelo(*). Una máquina de Turing puede simular el funcionamiento de un PC (comprobación complicada hasta un punto de locura alcanzable fácilmente por nuestros geeks actuales). Igualmente, un PC puede simular una máquina de Turing. Son computacionalmente equivalentes (no sé si me estoy dejando alguna condición para la equivalencia, así de memoria). Por eso dije, con un lenguaje relajado, que la máquina de Turing “está hecha”. Desde un punto de vista de complejidad computacional (P, NP, EXP, etc.) valen igual nuestros ordenadores que una máquina de Turing.

    Un ordenador cuántico nos haría pasar de una Máquina de Turing Determinista a una Máquina de Turing No Determinista. Lo cual haría que muchos algoritmos que hoy en día son exponenciales (no necesariamente todos) pasaran a ser polinómicos. Pero cuáles problemas son decidibles y cuáles no, es algo que no cambiaría.

    (*) Estrictamente no son equivalentes, puesto que para ello se requeriría memoria infinita en nuestros ordenadores. Pero este no es el problema en los cálculos actuales sino el orden de magnitud de las fórmulas que calculan el coste computacional (el “tiempo”) de los algoritmos. Si tenemos pc’s capaces de instalar Windows Vista y guardar las colecciones de películas y series de TV de mis compañeros de oficina, es que podemos considerar nuestra memoria como virtualmente infinita.

  9. mimetist | 13 de December de 2006 | 10:26

    Pensaba que un Ordenador Cuántico funcionaría igual que uno “normal” pero aumentando enormemente el número de operaciones por segundo…

  10. JuanPablo | 14 de December de 2006 | 13:18

    la demostración de Navier Stokes se cayó, la propia autora reconoció que había un error: http://comet.lehman.cuny.edu/sormani/others/smith.html

    (sin embargo, fue un buen intento, con una técnica clásica de comparaciones a la Perron, diferente a la línea de ataque del problema que está de moda ahora)

  11. neok | 14 de December de 2006 | 13:29

    JuanPablo en el enlace que pongo al lado, explicabamos que había noticias sobre ese problema, y días después (creo) dijimos lo que comentas, que había un error.

  12. JuanPablo | 14 de December de 2006 | 20:38

    ah, no vi la aclaración!

Comentarios cerrados.