La hipótesis de Riemann y el problema P = NP.

La hipotesis de Riemann (HR) es como una hidra de muchas cabezas que surge donde no se le espera. La fundación Clay promete un millón de dólares por la solución de los problemas del milenio, pero puede encontrarse con un problema inesperado. Si un matemático prueba en primer lugar la implicación \(\textbf{HR}\Longrightarrow \mathbf{P}\ne\mathbf{NP}\) y después otro matemático prueba HR. ¿Cómo han de repartirse los dos millones entre los dos matemáticos?

Trataremos de entender porqué HR, como dios, tiene el don de la ubicuidad.

La hipótesis de Riemann.

La hipótesis de Riemann surge al tratar de estudiar la distribución de los números primos. Gauss, cuando tenía un rato libre se dedicaba a contar cuántos primos había en un grupo de 1000 números consecutivos, llegó durante su vida hasta 2 millones. Observando los datos llegó a la conclusión de que el número de primos desde \(1\) hasta un \(x\) dado es aproximadamente
$$\pi(x)\approx \int_2^x\frac{dt}{\log t}.$$
La HR es la afirmación de que el error está acotado
$$\pi(x)= \int_2^x\frac{dt}{\log t}+ E(x),\qquad |E(x)|\le\frac{1}{8\pi}\sqrt{x}\log x \quad\text{si $x>2657$}.$$
Pero hay muchas otras afirmaciones equivalentes, por ejemplo que los ceros \(\rho\) de la función \(\zeta(s)\) de Riemann tales que \(\mathrm{Re}(\rho)>0\) verifican todos que \(\mathrm{Re}(s)=\frac12\).

Explicamos hoy la relación entre dos problemas, la hipótesis de Riemann y el problema ¿\(\mathbf{P}=\mathbf{NP}\)? Que las respuestas a estas dos preguntas tengan algo que ver es una de estas sorpresas a la que la Matemática nos tiene acostumbrados.

La hipótesis de Riemann generalizada.

La función zeta de Riemann es la mas simple de toda un conjunto de funciones con propiedades análogas las funciones \(L\). Por ejemplo cada extensión algebraica \(\mathbf{K}\) de \(\mathbf{Q}\) tiene un anillo de números enteros asociados (un ejemplo son los enteros de Gauss, los números de la forma \(a+bi\) con \(a\) y \(b\) enteros racionales). Estos anillos juegan un papel esencial, por ejemplo, en la solución de ecuaciones diofánticas y poseen sus propios números (o ideales) primos. La distribución de estos primos está asociada a una función zeta \(\zeta_{\mathbf{K}}(s)\) con propiedades similares a la función \(\zeta(s)\) de Riemann. Se conjetura que estas funciones cumplen la HR, es decir que sus ceros no triviales estén en la recta crítica \(\mathrm{Re}(s)=\frac12\). Esta es la que se llama la Hipótesis de Riemann Generalizada HRG.

El problema ¿P = NP?

Desde el advenimiento de los ordenadores nos hemos acostumbrado a los algoritmos, un algoritmo es como una receta para resolver un tipo de problemas. Por ejemplo una aplicación en nuestro teléfono busca el camino mas corto para desplazarnos a un determinado lugar. Otra aplicación nos determina que canción estamos oyendo en la radio.

Cada instancia de un problema es finita, y con una adecuada codificación se convierte en un número. Un tipo importante de algoritmo son los de decisión que nos dan una respuesta si o no a cada instancia que le presentamos. De manera que el algoritmo recibe un número natural y nos devuelve un si o un no, según el caso. Son este tipo de problemas los que nos interesan en esta entrada.

Es importante entender lo que decimos con «una adecuada codificación». Por ejemplo
si el dato de un problema es un conjunto de dos números \((24,391)\), podemos interpretar este dato como un número escrito en base 13, con el conjunto de dígitos \(\{0\,1\,2\,3\,4\,5\,6\,7\,8\,9\,)\,(\,,\}\) Desde este punto de vista una novela no es mas que un número natural.

Los estudiosos de los algoritmos clasifican los problemas en clases. Y debemos familiarizarnos con algunas de ellas:

Clases de problemas: La clase P.

La clase mas simple de problemas son los que tienen solución eficiente. Por eficiente entendemos que tenemos un algoritmo que los resuelve en un tiempo razonable. Por ejemplo el problema de dados dos números \((a,b)\) decidir si \(a\) divide a \(b\) o no. Solo tenemos que dividir \(b\) entre \(a\) y ver si obtenemos el resto \(=0\). Jack Edmonds en 1965 definió esta clase de problemas en un artículo con nombre poético: Paseos, árboles y flores (Paths, trees and flowers).

Técnicamente un problema está en \(\mathbf{P}\) si existe un algoritmo que resuelve cada instancia del problema en un tiempo menor que \(C |n|^k\) donde \(|n|\) es el tamaño en bits del problema y \(C\) y \(k\) son constantes (independientes de \(n\)).

La clase NP.

Un problema está en la clase \(\mathbf{NP}\) si para cada instancia positiva del problema \(n\), existe una prueba \(m\) que es fácil de comprobar. Es decir dada la pareja \((n,m)\) existe una verificación en tiempo polinómico de que \(n\) es instancia positiva. Pero si solo nos dan \(n\), no sabemos quien es \(m\).

Por ejemplo dado un conjunto de números naturales \((a_1, a_2, \dots, a_n, b)\) ¿existe un subconjunto de los \(a_j\) que sumen exactamente \(b\)? Hay \(2^n\) subconjuntos de los números \(a_j\), por tanto no es posible una búsqueda exhaustiva en tiempo polinómico. Sin embargo si nos dan un subconjunto particular, es muy fácil sumar y ver si realmente es igual a \(b\).

Hay una enorme cantidad de problemas prácticos que están en la clase \(\mathbf{NP}\). Además muchos de ellos, los llamados problemas \(\mathbf{NP}\) completos, tienen la propiedad de que si ese problema estuviera en la clase \(\mathbf{P}\) entonces todos los problemas de la clase \(\mathbf{NP}\) estarían en la clase \(\mathbf{P}\). El problema citado anteriormente de la suma parcial es \(\mathbf{NP}\) completo. Si alguien encuentra un algoritmo para resolverlo en tiempo polinómico, entonces se tendría \(\mathbf{P}=\mathbf{NP}\).

Un problema está en \(\mathbf{NP}\) si cada instancia positiva tiene una solución verificable eficientemente.

El problema ¿P = NP?

La existencia de problemas NP completos plantea la cuestión de si las clases \(\mathbf{P}\) y \(\mathbf{NP}\) coinciden.

La igualdad \(\mathbf{P} = \mathbf{NP}\) significaría que si para un tipo de problemas podemos verificar la solución eficientemente, entonces podríamos también encontrar la solución eficientemente. Cuando tenemos una demostración de un teorema el trabajo de verificarla es mecánico y solo depende de la longitud de esa prueba, si fuese \(\mathbf{P} = \mathbf{NP}\) debería ser también posible encontrar las pruebas de manera eficiente en función de su longitud. Los matemáticos seríamos prescindibles. Por esto los especialistas en computación están convencidos de que  \(\mathbf{P}\ne\mathbf{NP}\).

Se prueba que un problema es \(\mathbf{NP}\)-completo si una solución de ese problema puede convertirse en una solución para cualquier otro problema en la clase \(\mathbf{NP}\). Se ha probado que los futuros ordenadores cuánticos (si llegan a ser una realidad) resolverán problemas muy difíciles como el de la factorización. Sin embargo los especialistas piensan que no resolverán los problemas \(\mathbf{NP}\)-completos.

El avance de la matemática me sugiere la siguiente observación. No sabemos qué tipo de máquinas son nuestros cerebros. Quizás podemos llamarlos ordenadores cuánticos. Parece que los matemáticos resuelven los problemas en tiempo polinómico. Es decir los matemáticos parecemos la prueba viviente de que los problemas \(\mathbf{NP}\)-completos pueden ser resueltos por los ordenadores cuánticos (o lo que quiera que sean nuestros cerebros). Esto apoya la posibilidad (para mí aterradora) de que \(\mathbf{P} = \mathbf{NP}\).

Pascal Koiran y la conexión de los dos problemas.

Uno de los problemas mas antiguos de la matemática es el de la solución de sistemas de ecuaciones. Los números complejos se inventaron para conseguir que cada polinomio tuviera el número adecuado de soluciones. Consideremos un sistema de ecuaciones en varias variables y de grado arbitrario
$$\begin{aligned}
f_1(x_1,\dots, x_n)&=0\\
f_2(x_1,\dots, x_n)&=0\\
\dots\\
f_s(x_1,\dots, x_n)&=0.
\end{aligned}
$$
(donde cada \(f_j\) es un polinomio). Nuestro problema es decidir si el sistema es compatible. Esto es ¿existen números complejos \((x_1,\dots, x_n)\in\mathbf{C}^n\) tales que satisfagan todo el sistema de ecuaciones?

Dada un conjunto finito de polinomios \(f_1\), \(\dots\), \(f_s\) en \(n\) variables y con coeficientes enteros, esto es \(f_j\in\mathbf{Z}[x_1,x_2,\dots,x_n]\), queremos saber si el sistema es compatible.
El teorema de los ceros de Hilbert nos dice que el sistema es incompatible precisamente si existen otros polinomios \(g_1\), \(\dots\), \(g_s\in \mathbf{Z}[x_1,x_2,\dots,x_n]\) tales que
$$f_1g_1+f_2g_2+\cdots + f_n g_n =c,$$
donde \(c\) es un número entero no nulo.

Denotamos por HN (Hilbert’s Nullstellensatz) la clase de problemas de determinar si un sistema de ecuaciones \(S=\{f_j=0, 1\le j\le s\}\) es compatible en los complejos.

Dificultad del problema HN.

Es relativamente fácil demostrar que cualquier instancia de un problema en la clase \(\mathbf{NP}\) se traduce en una instancia del problema HN. De manera que \(\mathrm{HN}\in \mathbf{P}\) implicaría \(\mathbf{NP}=\mathbf{P}\). Por esto esperamos que HN sea igual o mas complicado que cualquier problema en la clase \(\mathbf{NP}\).

Sin embargo hoy día no sabemos que HN no esté en la clase \(\mathbf{P}\).
Más fácil que demostrar que \(\mathrm{HN}\not\in \mathbf{P}\) sería probar la implicación \(\mathrm{HN}\not\in \mathbf{P}\Longrightarrow \mathbf{P}\ne \mathbf{NP}\). Esto daría nueva luz sobre el problema ¿\(\mathbf{P}=\mathbf{NP}\)?. Esta es la dirección en que se mueve el trabajo de Koiran.

Conexión con la hipótesis de Riemann.

Hasta 1996 la solución de un problema de tipo HN pasaba por un teorema efectivo del tipo de Hilbert ([7]) que daba una cota del grado de los polinomios \(g_j\). Esto permite reducir el problema a un problema lineal (de tamaño exponencial) para determinar los coeficientes de los \(g_j\). Pascal Koiran [5] tiene entonces la idea de trabajar módulo un número primo, es decir, plantear el problema de si existen soluciones en el cuerpo finito \(\mathbf{F}_p=\mathbf{Z}/(p\mathbf{Z})\).

El principal teorema de Koiran va a relacionar la compatibilidad del sistema con números complejos con la cantidad de primos para los que el sistema es compatible módulo \(p\).

Dado el sistema \(S\) y un número real \(x>2\) denotamos por \(\pi_S(x)\) el número de primos \(p\le x\) tales que el sistema \(S\) admite solución en \(\mathbf{F}_p\). El principal teorema de Koiran establece que existen dos números \(A\) y \(x_0\) que dependen del sistema y que son de tamaño polinómico en función del tamaño de \(S\) tales que:

(a) Si el sistema \(S\) no admite soluciones en números complejos, entonces
\(\pi_S(x)\le A\), para todo \(x>x_0\).

(b) Si el sistema \(S\) admite soluciones en \(\mathbf{C}\) entonces \(\pi_S(x_0)>8A(\log A+3)\).

Esto permite aplicar métodos muy diferentes a los anteriores para resolver el problema HN. Pero todavía no son suficientes para probar que nuestro problema HN esté en la clase \(\mathbf{NP}\).

Lo que está claro es que ahora es importante contar los primos \(p\) para los que el sistema de ecuaciones es compatible y contar primos está estrechamente relacionado con la hipótesis de Riemann.

Aplicación del teorema de Chebotarëv.

Nuestro problema se ha convertido en el de estudiar para qué primos \(p\) es el sistema compatible en \(\mathbf{F}_p\). Si el sistema, con coeficientes en \(\mathbf{Z}\), admite soluciones complejas las admite algebraicas, de este modo entra en juego una extensión algebráica y nos interesa la distribución de los primos en el anillo de los enteros correspondientes.

Dirichlet probó que en toda progresión aritmética \(a+nb\) donde el máximo común divisor de \(a\) y \(b\) sea 1, existen infinitos números primos. Mas aún los primos módulo \(b\) están igualmente repartidos entre las distintas clases \(a\) primas con \(b\). Chebotarëv dió una generalización de este hecho, explicando como se distribuyen los primos en las extensiones algebráicas. Admitiendo la hipótesis generalizada de Riemann \(\textbf{HGR}\) Odlyzko y Lagarias dieron en 1977 una cota del error en el teorema de Chebotarëv.

De este modo la hipótesis de Riemann aparece en el problema. En multitud de algoritmos aparecen los números primos y su distribución está regida por la hipótesis de Riemann.

La conexión con nuestro problema es que el teorema de Chebotarëv en su versión efectiva permite caracterizar la probabilidad de que un primo esté contado o no en \(\pi_S(x)\).

 

La situación actual de HN.

Koiran prueba, admitiendo la HRG, que el problema HN está en la clase llamada \(\mathbf{AM}\), que no definiremos aquí. Lo que sí es cierto es que se tiene las inclusiones $$\mathbf{P}\subset \mathbf{NP}\subset\mathbf{AM},$$ y que todas estas clases coinciden si \(\mathbf{P}=\mathbf{NP}\). Por esto si HN no está en \(\mathbf{P}\) y suponemos la hipótesis de Riemann generalizada HRG entonces \(\mathbf{P}\ne\mathbf{NP}\), ya que en ese caso \(\mathbf{P}\ne \mathbf{AM}\).

Por tanto si suponemos la hipótesis de Riemann generalizada una manera de atacar el problema ¿\(\mathbf{P}=\mathbf{NP}\)? es probar que HN es suficientemente complicado.

En Marzo Maurice Rojas y Yuyu Zhu [6] han vuelto sobre los argumentos de Koiran, han extendido sus resultados al problema de la determinación de la dimensión del conjunto de soluciones del sistema de ecuaciones. De esta manera han conseguido rebajar la dependencia de la hipótesis de Riemann aunque no anularla completamente. El trabajo de Rojas y Zhu sobre el tema me ha dado pie para recordar el trabajo de Koiran.

Para saber mas.

La hipótesis de Riemann y el problema ¿\(\mathbf{P}=\mathbf{NP}\)? son tan populares que es difícil elegir.  Un libro que trata de explicar el problema ¿\(\mathbf{P}=\mathbf{NP}\)? sin matemáticas es

[1] L. Fortnow, «The golden ticket. P, NP, and the Search for the Impossible», Princeton University Press, 2013.

Del mismo autor encontramos en la web un artículo sobre la situación del problema:

[2] L. Fortnow, «The Status of the P versus NP problem«,  Comm. of the ACM, 52 (2009) 78–86.

Libros  de divulgación sobre la hipótesis de Riemann hay muchos mi preferido con mucho es:

[3] Marcus de Sautoy, La música de los números primos. El acantilado, 2013.

El teorema de Chebotarëv está muy bien contado, adornado con muchas notas históricas en el artículo

[4] P. Stevenhagen and H. W. Lenstra, Jr., Chebotarëv and his Density Theorem, Math. Intelligencer, 18 (1996) 26–36.

El que quiera profundizar puede leer los artículos originales:

[5] Pascal Koiran, Hilbert’s Nullstellensatz Is in the Polynomial Hierarchy, J. Complexity, 12 (1996) 273-286.

[6] Maurice Rojas, Yuyu Zhu, Dedekind zeta zeroes and faster complex dimension computation, arXiv:1803.04104

[7] W. D. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann of Math. (2) 126 (1987) 577-591.