You are currently browsing the category archive for the ‘Problemas del Milenio’ category.

Un problema puede ser más o menos difícil de resolver. La complejidad computacional pretende clasificar los problemas computacionales desde el punto de vista de cuanto cuesta resolverlos. Y para cuantificar esta dificultad de una manera teórica y objetiva, lo que se hace es ver como varia el tiempo de resolución con el tamaño de la entrada.

De esta manera, un problema perteneciente a la clase P, un problema resoluble en tiempo polinómico, es un problema cuyo tiempo de resolución es una función polinómica del tamaño de la entrada (si crece poco el tamaño de la entrada, crece poco el tiempo que tardamos en resolverlo, lo cual hace que estos problemas sean tratables).

¿Y qué quiere decir que un problema es de clase NP? Son aquellos problemas para los que es difícil encontrar una solución pero fácil verificarla, es decir, no se conoce ningún algoritmo polinómico que nos encuentre una solución pero si lo existe para comprobar que efectivamente lo es.

Para aclarar la definición anterior, pongamos un ejemplo: el problema del viajante de comercio. Dado un conjunto de ciudades, encontrar una ruta para un comerciante de manera que pase por TODAS las ciudades UNA ÚNICA vez. Este problema se traduce en encontrar un ciclo Hamiltoniano en un grafo. Un crecimiento moderado en el número de ciudades implicadas hace que el problema se vuelva prácticamente intratable. Sin embargo, si nos dan ya una solución, una ruta, es prácticamente trivial comprobar si es un ciclo hamiltoniano o no.

El problema P vs NP pretende demostrar si estos dos conjuntos son o no el mismo.

Dos definiciones complementarias para terminar.

  • Un problema es NP-completo si es un problema NP de los mas difíciles, dejémoslo ahí. El problema anterior es un problema de esta clase. Una propiedad que tienen estos problemas es que son todos equivalentes, desde el punto de vista de complejidad computacional, entre si, es decir, existe un algoritmo que traduce cualquier problema NP-completo en cualquier otro en tiempo polinómico. De manera que, si lográramos un algoritmo en P que resolviera uno de ellos, tendríamos un algoritmo en P para todos ellos (traducimos el otro problema al primero en tiempo polinómico, lo resolvemos en tiempo polinómico y traducimos la solución a una solución del original en tiempo polinómico).
  • Un problema es NP-duro si es, al menos, tan difícil como NP.

 

 

Anuncios

Solo referenciar este post de Francisco R. Villatoro sobre la demostración de Otelbaev del problema del milenio referente a las ecuaciones de Navier-Stokes.

Las ideas principales que comenta son:

  1. Se ha encontrado un contraejemplo (usuario “sup” de dxdy.ru + Stephen Montgomery-Smith + Terry Tao) al principal teorema del artículo, el teorema 6.1, lo que invalida completamente la demostración de Otelbaev.
  2. El matemático Terry Tao, en su artículo “Finite time blowup for an averaged three-dimensional Navier-Stokes equation“, demuestra que la técnica utilizada para atacar el problema no es suficiente, es decir, que no vamos a poder resolver nunca el problema con la técnica que utilizó Otelbaev.
  3. Parece que tenemos problema para rato, segun el propio Tao.

Para mas detalle, al post referido en el inicio de esta entrada 🙂

En las Jornadas sobre los problemas del milenio celebradas en Barcelona del 1 al 3 de junio de 2011, Diego Córdoba dió una charla sobre el problema Clay de las ecuaciones de Navier-Stokes para la que escribió estas notas.

Un fluido es ideal si es incompresible, homogéneo  y perfecto.

La idea del problema consiste en determinar si:

…un fluido incompresible con energía finita puede desarrollar singularidades en tiempo finitos.

Mas formalmente, si consideramos un fluido viscoso (\nu > 0), homogéneo (\rho = 1) e incompresible (\nabla \cdot u = 0), tenemos:

u_t + u \cdot \nabla u = - \nabla p + \nu \Delta u + f con \nu >0, x \in \mathbb{R}^3, t \geq 0

\nabla \cdot u = 0

u(x,0) = u_0

donde cada partícula en el tiempo t está en la posición x = (x_1,x_2,x_3) del dominio que ocupa el fluido \Omega \subset \mathbb{R}^3, u(x,t) = (u_1(x,t), u_2(x,t), u_3(x,t)) es el campo de velocidades, p = p(x,t) son las presiones en el seno del fluido y \rho = \rho(x,t) es la densidad. Además, \nu = cte \geq 0 es la viscosidad y f la fuerza externa.

La fuerza exterior  debe verificar:

|\partial_x^\alpha\partial_t^m f| \leq C_{\alpha,k,m}(1+|x|+t)^{-k} para todo \alpha, k, m > 0

y el dato inicial las siguientes condiciones de regularidad:

|\partial_x^\alpha u_{0i}| \leq C_{\alpha,k}(1+|x|)^{-k} para todo \alpha, k > 0

Las soluciones (u,p) admisibles para x \in \mathbb{R}^3 estan o en C^{\infty}(\mathbb{R}^3 \times [0,\infty)) con decaimiento en el infinito de la presión y de energía finita, es decir, \int_{\mathbb{R}^3} |u|^2 dx < \infty para todo t, o estan en C^{\infty}(\mathbb{T}^3 \times [0,\infty)) periódicas y la presión de media cero.

Sea u_0 satisfaciendo las condiciones de regularidad. El problema del Instituto Clay consiste, entonces, en determinar si siempre existen soluciones admisibles para u_0 o si existe algún caso en que no.

La hipótesis de Rieman dice que todos los ceros no triviales de la función zeta de Riemann:

\zeta(z) = \sum_{n=1}^{\infty} \frac{1}{n^z}

tienen parte real \frac{1}{2}.

En el entretenido libro “La música de los números primos” de Marcus de Sautoy, éste comenta la posibilidad de que la teoría de números y la física estén mas estrechamente relacionadas de lo que pensamos:

Los físicos creen que la razón por la que los ceros de Riemann deben situarse todos sobre la recta es que terminarán por ser las frecuencias de un tambor matemático. A un cero que se situara fuera de la recta le correspondería una frecuencia imaginaria prohibida por la teoría.

Y para afianzar esta idea, comenta un problema clásico de hidrodinámica resuelto por Bernhard Riemann argumentando de la misma manera:

El problema se refiere a una esfera de fluido en rotación que se mantiene unida gracias a interacciones gravitacionales recíprocas entre las partículas que la componen. Una estrella, por ejemplo, es una enorme bola de gas giratorio que se mantiene unido por su propia gravedad. La cuestión es: ¿qué sucederá con la bola si se le da una patada?¿Se limitará a temblar ligeramente o se desitegrará? Para responder a estas preguntas es necesario determinar si ciertos números imaginarios determinados están o no alineados. Si lo están, la esfera de fluido en rotación quedará intacta.

Los Nachlass son un conjunto de notas inéditas de Riemann que están en la biblioteca de Gotinga. Cuenta el libro que cuando el físico Jon Keating pidió dos partes de los Nachlass, una correspondiente a sus intentos de demostración de la hipotesis de Riemann y otra a sus estudios en hidrodinámica, el bibliotecario le entrego un único grupo de documentos. De ahí que Marcus escriba:

Una vez más, los Nachlass revelaban hasta qué punto Riemann se adelantó a su tiempo. Es imposible que no fuera consciente del significado que implicaba su solución al problema de dinámica de fluidos. Su método había demostrado por qué cietos números imaginarios que aparecían en su análisis de la esfera de fluido se colocaban en línea recta; y al mismo tiempo -y en los mismos folios- estaba intentando demostrar por qué los ceros de su paisaje zeta se situaban todos sobre la misma línea.

 

octubre 2017
L M X J V S D
« Ago    
 1
2345678
9101112131415
16171819202122
23242526272829
3031