Abierto principal computacional de problemas en la eliminación de cuantificadores?

Question

Un lenguaje se dice que la eliminación de cuantificador si todos los de primer orden-la lógica de la frase en el idioma puede ser demostrado ser equivalente a la de un cuantificador libre de sentencia, es decir, una frase sin ningún tipo de $\forall$s o $\exists$s. Un ejemplo es la teoría de la real campos cerrados (como $\mathbb{R}$), considera que con las cuatro operaciones básicas, la igualdad ($=$) y las desigualdades ($<$, $>$).

Pregunta: ¿qué tan rápido puede un algoritmo que realiza la eliminación de cuantificador ser? Por cuánto son los actuales algoritmos (como los que proceden por cilíndrico de descomposición) peor que el mejor de los algoritmos que se concebible posible? ¿Cuáles son, en breve, los principales abierto computacional de problemas en la eliminación de cuantificadores?

(Podemos intentar restringir el debate a $\mathbb{R}$, a pesar de que otros "útil" teorías también me interesa.)

Hasta donde yo sé, la situación es la siguiente: en general, no son de primer orden de las frases en $k$ variables que no son equivalentes a cualquier cuantificador libre de frases de longitud de menos de $\exp(\exp(C k))$; esto significa, en particular, que en el peor de los casos el rendimiento de un programa de eliminación del cuantificador tiene que ser de al menos doblemente exponencial en $k$. Esto es coincidente con cilíndrica-descomposición de los algoritmos (corríjanme si me equivoco). Al mismo tiempo, si la fórmula original contiene sólo $\exists$s o sólo $\forall$s, luego de un algoritmo que es individualmente exponencial en $k$ es conocido. (Estoy pasando por un muy rápida lectura de Basu, Abadejo, Roy, los Algoritmos en la Geometría Algebraica Real; todos los errores son míos.)

El segundo caso - en el que exponencial límites son conocidos - es importante, ya que abarca todos los casos de la forma de "probar esta fórmula tiene para todos los $x_1, x_2,\cdots, x_k$".

Es este el final de la historia, o es que hay una subárea en donde un montón de trabajo que podría permanecer a hacer?

---

Así, parece existir un interés real en esta pregunta, pero la respuesta no como tal todavía. Permítanme sugerir lo que sería muy bonito como una respuesta: un par de problemas abiertos sobre el tema, difícil, pero no imposible, con instrucciones que son ordenadas suficiente para los matemáticos, pero también lo suficientemente cerca como para la práctica real de que su solución es probable que sea útil.

Por ejemplo: ¿la reducción de la teoría existencial de $\mathbb{R}$ a $k$-SAT ser un problema?

Answer 1

El problema del enfoque actual en esta área, ejemplificado por el libro de Basu, Abadejo, Roy, "Algoritmos en la Geometría Algebraica Real" es que uno termina con el caso más simple: la comprobación de la no-vacío de un verdadero conjunto algebraico $S$, y el único bien analizada clase de algoritmos para resolver conduce a la caza de las raíces de un polinomio univariado de grado, al menos, el número de componentes conectados de $S$. Peor aún, si $S=V_{\mathbb{R}}(f_1,\dots,f_k)$, en lugar de mirar el ideal $(f_1,\dots,f_k)\in\mathbb{R}[x_1,\dots, x_n]$ una ve $V_{\mathbb{R}}(\sum_{j=1}^k f_j^2)$, lo que conduce a la voladura de grados por 2.

Un tema interesante sería tratar de puente con las sumas de los cuadrados de los métodos basados en la geometría algebraica real. (Que son en la práctica computacionalmente más factible, mediante el uso de semidefinite de programación). El último se puede leer acerca de, por ejemplo, de "Semidefinite y Optimización Convexa de la Geometría Algebraica".

Hay muchos problemas abiertos en el último sí, algunos de ellos de número de la teoría de sabor. E. g., entender cuando un polinomio $f$ con coeficientes racionales $f=\sum_{j=1}^m h_j^2 \in\mathbb{Q}[x_1,\dots, x_n]$, con cada una de las $h_j\in\mathbb{R}[x_1,\dots, x_n]$ (es decir, $f$ es la suma de los cuadrados de polinomios con coeficientes reales) puede ser una suma de los cuadrados de polinomios con coeficientes racionales, $f=\sum_{j=1}^{m'} g_j^2$, con cada una de las $g_j\in\mathbb{Q}[x_1,\dots, x_n]$. El estado del arte sobre este problema está aquí, en la charla de la C. Scheiderer.

Una mucho más famoso abrir problema no es la complejidad de la viabilidad problema lineal de la matriz de las desigualdades: decidir el vacío de $$S(A_0,\dots,A_m):=\{x\in\mathbb{R}^m\mid A_0+\sum_{j=1}^m x_j A_j\succeq 0\},$$ where $A_j$ are symmetric matrices, and $B\succeq 0$ stands for "$B$ is positive semidefinite". See e.g. this. There has been no progress on this problem since Ramana's 1997 paper. The related problem is semidefinite programming, a.k.a. SDP: minimize a linear function on $S(A_0,\dots,A_m)$. Es una generalización natural de programación lineal (LP), y se ha convertido en muy popular en diversas áreas, debido a que su expresivo poderes. El capítulo 2 de este libro es una introducción a la SDP.

La relación entre el SDP y la viabilidad problema lineal de la matriz de las desigualdades es similar a la relación entre LP y la viabilidad problema de "ordinario" desigualdades lineales. Es decir, uno puede resolver el problema de minimización de manera eficiente iff uno puede solucionar el problema de viabilidad de forma eficiente, esto es conocido como "equivalencia de la optimización y de la separación". Khachiyan y Porkolab escribió un papel , donde uno puede encontrar un número de construcciones que ilustran cómo mucho más delicado $S(A_0,\dots,A_m)$ son, en comparación con el "ordinario" de los poliedros.