1. Problema P (dificil de encontrar) contra NP (fácil de verificar):
Este problema, planteado de manera independiente en 1971 por Stephen Cook y por Leonid Levin se considera hoy dia el problema central de la computación teórica.
La cuestión es que existen, por una parte, problemas resolubles de manera determinista mediante algoritmos polinómicos y en un tiempo polinomial, como puede ser, por ejemplo la resolución de ecuaciones, la realización de sumas, productos, etc., pudiendo acotar el tiempo de resolución, mas o menos largo, de una manera aceptable. Estos son los problemas P.
Sin embargo, también existen problemas NP que pueden resolverse de forma indeterminista probando una solución conjeturada. Esta comprobación es de una gran rapidez en comparación con el tiempo polinomial necesario en general para la resolución determinista de los problemas P.
Está claro que todo problema P es también NP, esto es, todo problema resoluble en tiempo polinomial mediante un algoritmo adecuado (P), es también un problema que admite una comprobación rápida (NP).
Pero, ¿y al revés?. ¿Existen problemas NP que no sean P?. Esto es, ¿existen problemas que admiten una comprobación de solución o no solución conjeturada y, en cambio, no admiten en tiempo polinomial una resolución algoritmica?
En el cálculo computacional pueden presentarse problemas en donde el número de alternativas posibles para una determinada condición de proceso es tan grande que ni siquiera con las supercomputadores existentes aún en nuestra tecnología se podrían afrontar en toda la vida de un ser humano, pues no tendría para ello el suficiente tiempo (es el problema P). En cambio, la verificación de que una determinada alternativa verifica la condición de proceso es algo pràcticamente instantáneo (es el problema NP).
Si, por ejemplo, queremos colocar 6000 libros en 200 estantes, de modo que se cumpla la condición de que no estén juntos ciertos libros de diferente materia, nos encontramos que el número de alternativas posibles podría superar al número de átomos de la Vía Láctea, con lo cual, el determinarlas todas (problema P - difícil de encontrar) es precisamente eso, muy difícil en la actual tecnología de la computación. En cambio, el verificar una de estas alternativas como válida, cuando alguien conjetura una solución, (problema NP - fácil de verificar) es inmediato.
En estos ejemplos, en los que el problema NP es comprobable de inmediato, pero el problema P parece no existir, ¿se debe esto a que realmente el problema P no es posible o bien que no se tiene la tecnología computacional adecuada para su resolución de forma algoritmica en tiempo polinomial?
Esta es la pregunta no contestada que da consistencia al problema. Entre los ejemplos actuales más candentes está el de la criptografía y la comprobación de claves informaticas (NP) en contraposición al problema de generación algoritmica de tales claves en un tiempo polinomial (P).
2. La conjetura de Hodge:
Esta conjetura afirma que para ciertos espacios particulares denominados Variedades Proyectivas Algebráicas, las partes llamadas Ciclos de Hodge son realmente combinaciones de Ciclos Algebráicos.
3. Ecuaciones de Navier-Stokes:
Existe desde el siglo XIX un conjunto de ecuaciones que permite estudiar las turbulencias en los líquidos y en los gases, sin que exista una teoría matemática que las fundamente. El desafío consiste en encontrar tal fundamentación.
4. La Conjetura de Poincaré:
Para n ³ 3, la única superficie compacta, orientable y simplemente conexa es homeomorfa a la esfera Sn. Esto es, la superficie de una esfera, en cualquier número de dimensiones mayor que 2 puede contraerse hasta un único punto de forma continua, dicho de otro modo, la superficie de una esfera es simplemente conexa.
5. La Hipótesis de Riemann:
Afirma la Hipótesis de Riemann que las partes reales de los ceros, a+bi, de la llamada Función Zeta son siempre a = 1/2, es decir, están alineados. Esta función es
6. La Teoría de Yang-Mills:
La llamada Teoría de Yang-Mills describe las partículas elementales de la Mecánica Cuántica, y sus Interacciones fuertes usando estructuras geométricas.
Estas descripciones teóricas han sido comprobadas experimentalmente en laboratorio y también obtenidas mediante simulación computacional, pero no existe edificada una teoría matemática que establezca un fundamento para las mismas.
7. La Conjetura de Birch y Swinnerton-Dyer:
Aún cuando ya sabemos que no existen métodos generales para resolver las ecuaciones diofánticas tal como pedía el décimo de los problemas de Hilbert (demostrado en 1970 por Yu. V. Matiyasevich), sin embargo, la conjetura de Birch y Swinnerton-Dyer afirma que en el caso de las soluciones de las ecuaciones diofánticas generales, cuando éstas son los puntos de una variedad abeliana, el conjunto de los puntos que son soluciones racionales de las mismas depende de la función zeta, z(n), asociada, de modo que si z(1) = 0, hay infinitas soluciones, y si z(1)
0, el número de soluciones es finito.
No hay comentarios:
Publicar un comentario