Teoría existencial de los números reales

En lógica matemática, teoría de la complejidad computacional y ciencias de la computación, la teoría existencial de los números reales es el conjunto de todas las oraciones verdaderas de la forma

$${\displaystyle \exists X_{1}\cdots \exists X_{n}\,F(X_{1},\dots ,X_{n}),}$$

donde las variables ${\displaystyle X_{i}}$ se interpretan como valores reales, y donde ${\displaystyle F(X_{1},\dots X_{n})}$ es una fórmula bien formada que implica igualdades y desigualdades de polinomios reales. Una oración de esta forma es verdadera si es posible encontrar valores para todas las variables que, al sustituirlas en la fórmula ${\displaystyle F}$, la hacen verdadera.^[1]​

El problema de decisión de la teoría existencial de los números reales es el problema de encontrar un algoritmo que determine, para cada oración, si es verdadera o falsa. De manera equivalente, es el problema de comprobar si un conjunto semialgebraico dado no es vacío.^[1]​ Este problema de decisión es NP-difícil y reside en el PSPACE,^[2]​ lo que le confiere una complejidad significativamente menor que el procedimiento ideado por Alfred Tarski de la eliminación de cuantificadores para decidir enunciados en la teoría de primer orden de los números reales sin la restricción de cuantificadores existencial.^[1]​ Sin embargo, en la práctica, los métodos generales de la teoría de primer orden siguen siendo la opción preferida para resolver estos problemas.^[3]​

La clase de complejidad ${\displaystyle \exists \mathbb {R} }$ se ha definido para describir la clase de problemas computacionales que pueden traducirse a oraciones equivalentes de esta forma. En teoría de la complejidad estructural, se encuentra entre NP y PSPACE. Muchos problemas naturales en teoría de grafos geométricos, especialmente los problemas de reconocimiento de grafos de intersección geométricos y el enderezamiento de las aristas de representaciones de grafos con puntos de cruce, pertenecen a ${\displaystyle \exists \mathbb {R} }$ y son completos para esta clase. En este caso, la completitud significa que existe una traducción en la dirección inversa, de una oración arbitraria sobre los números reales a una instancia equivalente del problema dado.^[4]​

En lógica matemática, una teoría es un lenguaje formal que consiste en un conjunto de sentencias escritas utilizando un conjunto fijo de símbolos. La teoría de primer orden de cuerpos reales cerrados tiene los siguientes símbolos:^[5]​

• Las constantes 0 y 1
• Un conjunto numerable de variables ${\displaystyle X_{i}}$
• Las operaciones de suma, resta, multiplicación y (opcionalmente) división
• Los símbolos <, ≤,=, ≥, >, y ≠ para la comparación de valores reales
• Los conectores lógicos ∧, ∨, ¬, y ⇔
• Paréntesis
• El cuantificador universal ∀ (para todo) y el cuantificador existencial ∃ (existe).

Una secuencia de estos símbolos forma una oración que pertenece a la teoría de primer orden de los reales si está gramaticalmente bien formada, todas sus variables están cuantificadas apropiadamente, y (cuando se interpreta como una afirmación matemática acerca de los números reales) es una afirmación verdadera. Como mostró Tarski, esta teoría puede ser descrita por un esquema de axiomas y un procedimiento de decisión que es completo y efectivo: para cada oración completamente cuantificada y gramatical, la oración o su negación (pero no ambas) pueden derivarse de los axiomas. La misma teoría describe cada cuerpo real cerrado, no solo los números reales.^[6]​ Sin embargo, hay otros sistemas numéricos que no son descritos con precisión por estos axiomas. En particular, la teoría definida de la misma manera para los números enteros en lugar de los números reales es indecidible, incluso para oraciones existenciales (ecuaciones diofánticas) según el teorema de Matiyasevich.^[5]​^[7]​

La teoría existencial de los reales es un fragmento de la teoría de primer orden, que consiste en oraciones en las que todos los cuantificadores son existenciales y aparecen antes de cualquier otro símbolo. Es decir, es el conjunto de todas las oraciones verdaderas de la forma

$${\displaystyle \exists X_{1}\cdots \exists X_{n}\,F(X_{1},\dots ,X_{n}),}$$

donde ${\displaystyle F(X_{1},\dots X_{n})}$ es una fórmula bien formada que implica igualdades y desigualdades de polinomios reales. El problema de decisión para la teoría existencial de los reales es el problema algorítmico de comprobar si una oración dada pertenece a esta teoría. De forma equivalente, para cadenas que superan las comprobaciones sintácticas básicas (utilizar los símbolos correctos con la sintaxis correcta y no tener variables no cuantificadas), el problema consiste en comprobar si la oración es una afirmación verdadera sobre los números reales. El conjunto de ${\displaystyle n}$-tuplas de números reales ${\displaystyle (X_{1},\dots X_{n})}$ para las que ${\displaystyle F(X_{1},\dots X_{n})}$ es verdadero se denomina conjunto semialgebraico, por lo que el problema de decisión para la teoría existencial de los reales puede reformularse, equivalentemente, como comprobar si un conjunto semialgebraico dado es no vacío.^[1]​

Para determinar la complejidad temporal del algoritmo necesario para abordar el problema de decisión de la teoría existencial de los reales, es importante contar con una medida del tamaño de la entrada. La medida más simple de este tipo es la longitud de una oración: es decir, el número de símbolos que contiene.^[5]​ Sin embargo, para lograr un análisis más preciso del comportamiento de los algoritmos para este problema, es conveniente descomponer el tamaño de entrada en varias variables, separando el número de variables a cuantificar, el número de polinomios dentro de la oración y el grado de estos polinomios.^[8]​

El número áureo ${\displaystyle \varphi }$ puede definirse como la raíz del polinomio ${\displaystyle x^{2}-x-1}$. Este polinomio tiene dos raíces, de las cuales solo una (la proporción áurea) es mayor que uno. Por lo tanto, la existencia de la proporción áurea puede expresarse mediante la oración:

$${\displaystyle \exists X_{1}(X_{1}>1\wedge X_{1}\times X_{1}-X_{1}-1=0).}$$.

Dado que la proporción áurea no es un número trascendente, esta es una oración verdadera y pertenece a la teoría existencial de los números reales. La respuesta al problema de decisión para la teoría existencial de los números reales, dada esta oración como entrada, es el valor booleano verdadero.

La desigualdad de las medias aritmética y geométrica establece que, para cada dos números no negativos ${\displaystyle x}$ y ${\displaystyle y}$, se cumple la siguiente desigualdad:

$${\displaystyle {\frac {x+y}{2}}\geq {\sqrt {xy}}.}$$

Como se mencionó anteriormente, se trata de una oración de primer orden sobre los números reales, pero con cuantificadores universales en lugar de existenciales, y que utiliza símbolos adicionales para la división, raíces cuadradas y el número 2, símbolos que no están permitidos en la teoría de primer orden de los reales. Sin embargo, al elevar al cuadrado ambos lados, se puede transformar en la siguiente oración existencial, que puede interpretarse como la pregunta de si la desigualdad tiene contraejemplos:

${\displaystyle \exists X_{1}\exists X_{2}{\bigl (}X_{1}\geq 0\wedge X_{2}\geq 0\wedge (X_{1}+X_{2})\times (X_{1}+X_{2})<(X_{1}+X_{1})\times (X_{2}+X_{2}){\bigr )}.}$

La respuesta al problema de decisión para la teoría existencial de los reales, dada esta oración como entrada, es el valor booleano falso: no hay contraejemplos. Por lo tanto, esta oración no pertenece a la teoría existencial de los reales, a pesar de tener la forma gramatical correcta.

El método de Alfred Tarski de eliminación de cuantificadores (1948) demostró que la teoría existencial de los reales (y, más generalmente, la teoría de primer orden de los reales) es algorítmicamente resoluble, pero sin un límite de complejidad elemental.^[9]​^[6]​. El método de la descomposición algebraica cilíndrica, de George E. Collins (1975), mejoró la dependencia temporal a doble exponencial,^[9]​^[10]​ de la forma

$${\displaystyle L^{3}(md)^{2^{O(n)}}}$$

donde ${\displaystyle L}$ es el número de bits necesarios para representar los coeficientes en la oración cuyo valor se va a determinar, ${\displaystyle m}$ es el número de polinomios en la oración, ${\displaystyle d}$ es su grado total y ${\displaystyle n}$ es el número de variables.^[8]​ Para 1988, Dima Grigoriev y Nicolai Vorobjov habían demostrado que la complejidad era exponencial en un polinomio de ${\displaystyle n}$,^[8]​^[11]​^[12]​

$${\displaystyle L(md)^{n^{2}}}$$

y en una secuencia de artículos publicados en 1992, James Renegar mejoró esto a una dependencia exponencial simple en ${\displaystyle n}$,^[8]​^[13]​^[14]​^[15]​

$${\displaystyle L\log L\log \log L(md)^{O(n)}.}$$

Mientras tanto, en 1988, John Canny describió otro algoritmo que también tiene dependencia temporal exponencial, pero solo complejidad espacial polinómica, es decir, demostró que el problema podía resolverse en PSPACE.^[2]​^[9]​

La complejidad computacional asintótica de estos algoritmos puede ser engañosa, ya que en la práctica solo pueden ejecutarse con entradas de tamaño muy pequeño. En una comparación de 1991, Hoon Hong estimó que el procedimiento doblemente exponencial de Collins podría resolver un problema cuyo tamaño se describe estableciendo todos los parámetros anteriores a 2, en menos de un segundo, mientras que los algoritmos de Grigoriev, Vorbjov y Renegar tardarían más de un millón de años.^[8]​ En 1993, Joos, Roy y Solernó sugirieron que debería ser posible realizar pequeñas modificaciones a los procedimientos de tiempo exponencial para hacerlos más rápidos en la práctica que la decisión algebraica cilíndrica, así como más rápidos en teoría.^[16]​ Sin embargo, en 2009, los métodos generales para la teoría de primer orden de los números reales seguían siendo superiores en la práctica a los algoritmos exponenciales simples especializados en la teoría existencial de los números reales.^[3]​

Varios problemas de complejidad computacional y de teoría de grafos geométricos pueden clasificarse como completos para la teoría existencial de los números reales. Es decir, cada problema de la teoría existencial de los números reales tiene una reducción de muchos a uno en tiempo polinómico para una instancia de uno de estos problemas, y a su vez, estos problemas son reducibles a la teoría existencial de los números reales.^[4]​^[17]​

Varios problemas de este tipo se centran en el reconocimiento de grafos de intersección de un tipo determinado. En estos problemas, la entrada es un grafo no dirigido, y el objetivo es determinar si las figuras geométricas de una clase específica pueden asociarse con los vértices del grafo de tal manera que dos vértices sean adyacentes en el grafo si, y solo si, sus figuras asociadas tienen una intersección no vacía. Los problemas de este tipo, que cumplen con la teoría existencial de los números reales, incluyen el reconocimiento de grafos de intersección de segmentos en el plano,^[4]​^[18]​^[5]​ el reconocimiento de grafos de disco unitario^[19]​ y el reconocimiento de grafos de intersección de conjuntos convexos en el plano.^[4]​

Para grafos dibujados en el plano sin cruces, el teorema de Fáry establece que se obtiene la misma clase de grafo plano independientemente de si las aristas del grafo se dibujan como segmentos de línea recta o como curvas arbitrarias. Sin embargo, esta equivalencia no se cumple para otros tipos de dibujo. Por ejemplo, aunque el número de cruce de un grafo (el número mínimo de cruces en un dibujo con aristas curvas arbitrarias) puede determinarse en NP, para la teoría existencial de los reales es completo determinar si existe un dibujo que alcance una cota dada en el número de cruces rectilíneos (el número mínimo de pares de aristas que se cruzan en cualquier dibujo con aristas dibujadas como segmentos de línea recta en el plano).^[4]​^[20]​

También es completo para la teoría existencial de los números reales comprobar si un grafo dado puede dibujarse en el plano con aristas rectas y con un conjunto dado de pares de aristas como cruces, o equivalentemente, si un dibujo curvo con cruces puede enderezarse de forma que conserve sus cruces.^[21]​

Otros problemas completos para la teoría existencial de los reales incluyen:

• El problema de la galería de arte para encontrar el menor número de puntos desde los cuales todos los puntos de un polígono dado sean visibles.^[22]​
• Entrenamiento de redes neuronales artificiales.^[23]​
• El problema de empaquetado para decidir si un conjunto dado de polígonos cabe en un contenedor cuadrado dado.^[24]​
• Reconocimiento de grafos de distancia unitaria y comprobación de si la dimensión de un grafo (o su dimensión euclídea) tiene como máximo un valor dado.^[9]​
• Extensibilidad de pseudolíneas (es decir, dada una familia de curvas en el plano, determinar si son homeomórficas a disposiciones de rectas).^[4]​^[25]​^[26]​
• Satisfacibilidad débil y fuerte de lógica cuántica geométrica en cualquier dimensión fija >2.^[27]​
• Comprobación de modelos de cadenas de Markov de intervalos con respecto a autómatas no ambiguos.^[28]​
• El algoritmo para el problema de Steinitz (dado un retículo, determinar si es la red de caras de un politopo convexo), incluso cuando se restringe a politopos de 4 dimensiones;^[29]​^[30]​
• Espacios de realización de la configuración de ciertos cuerpos convexos.^[31]​
• Diversas propiedades de equilibrios de Nash en juegos multijugador.^[32]​^[33]​^[34]​
• Incrustar un complejo abstracto dado de triángulos y cuadriláteros en el espacio euclídeo tridimensional;^[17]​
• Incrustar múltiples grafos en un conjunto de vértices compartido en el plano, de modo que todos los grafos se dibujen sin cruces.^[17]​
• Reconocer los grafos de visibilidad de conjuntos de puntos en un plano.^[17]​
• Satisfacibilidad (proyectiva o afín no trivial) de una ecuación entre dos términos sobre el producto vectorial.^[35]​
• Determinación del mínimo número de pendiente de un dibujo sin cruces de un grafo plano.^[36]​
• Reconocimiento de grafos que se pueden dibujar con todos los cruces en ángulos rectos.^[37]​
• El problema de evaluación parcial para el lenguaje de consulta MATLANG+matrices propias.^[38]​
• El problema de completar matrices de bajo rango.^[39]​

Con base en esto, la clase de complejidad ${\displaystyle \exists \mathbb {R} }$ se ha definido como el conjunto de problemas con una reducción de muchos a uno en tiempo polinomial a la teoría existencial de los reales.^[4]​

• Décimo problema de Hilbert, sobre la teoría existencial (indecidible) de los enteros.