He leído de Wikipedia sobre la Teoría de la Complejidad Geométrica (TGC) que (si no he entendido mal) es un programa para hacer frente a la $ P=NP $ problema utilizando métodos algebraicos.
Ese programa parece prometedor, pero me pregunto cuáles son sus resultados actuales.
¿Cuáles son los avances actuales de la Teoría de la Complejidad Geométrica?
Se trata más de un resultado negativo que positivo, por lo que puede que no sea lo que usted busca, pero yo lo considero un gran avance: Bürgisser, Ikenmeyer y Panova demostró que cierta forma muy fuerte de la teoría de la complejidad de la geometría no puede ser cierta. Una idea clave en la teoría de la complejidad geométrica es intentar separar los cierres de órbita de los polinomios determinantes y permanentes acolchados. Una forma especialmente optimista de conseguirlo es demostrar que alguna representación irreducible de $GL_{n^2}(\mathbb{C})$ se produce en un anillo de coordenadas pero no aparece en absoluto en el otro. El artículo mencionado demuestra que esta esperanza es demasiado optimista.
Sea $X=(X_{ij})_{1\le i,j\le n}$ sea un genérico $n\times n$ matriz y $F_1(X)={\rm det}(X)$ el grado $n$ polinomio homogéneo dado por el determinante. Sea $$ F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right] $$ que adopta la forma permanente de un $m\times m$ submatriz y se multiplica por la forma lineal preferida para obtener otro polinomio homogéneo de grado $n$ (también se puede utilizar la entrada $X_{11}$ en lugar de $X_{nn}$ ). Esta modificación se denomina acolchado . A continuación, defina el número $$ c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \} $$ donde $G$ es $GL(n^2)$ actuando sobre el espacio $V$ de dimensión $n^2$ donde $X$ vidas y, por tanto, también en el espacio de grado $n$ funciones polinómicas de $X$ . En $\overline{G\cdot F_i}$ son cierres Zariski de órbitas. La gran conjetura en el área o Hipótesis de Valiant (una versión compleja de ${\rm P}\neq{\rm NP}$ ) es que $c(m)$ crece más rápido que cualquier polinomio en $m$ .
Ahora bien $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$ entonces se tiene una $G$ -equivariante $$ \mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d $$ entre grado $d$ partes de los anillos de coordenadas de estos cierres de órbita. Así que el juego consiste en tratar de demostrar que esto no sucede, para $n$ insuficientemente grande en relación con $m$ demostrando la existencia de un obstrucción por multiplicidad es decir, una representación irreducible $\lambda$ cuyas multiplicidades satisfacen $$ {\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d) $$ o en el plano de los ideales $$ {\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ . $$
Un enfoque optimista es intentar demostrar que existen obstáculos a la aparición es decir, $\lambda$ tal que ${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$ y ${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$ . Esta esperanza se ha desvanecido en los trabajos de Bürgisser, Ikenmeyer y Panova mencionados por Timothy. Sin embargo, la posibilidad de obstrucciones por multiplicidad sigue abierta.
Creo que el enfoque de Mulmuley es intentar demostrar la existencia de tales obstrucciones de multiplicidad aprovechando todas las herramientas disponibles de la teoría de la representación para el cálculo de estas multiplicidades. Personalmente, nunca me ha gustado este enfoque. Habiendo estudiado con cierta profundidad la teoría de invariantes del siglo XIX, me parece más natural abordar el problema de la separación de órbitas utilizando las herramientas explícitas de aquella época. Este artículo de Grochow también parece apuntar en una dirección similar (sospecho que el tercer artículo mencionado por Joseph va en la misma línea). En el lenguaje clásico (véase Turnbull ou Littlewood ), hay que explícitamente construir a concomitante mixto que desaparece en $F_1$ pero no en $F_2$ . También hay que hacerlo infinitas veces (en $m$ ) para establecer la propiedad de crecimiento superpolinómico. Tal (grado $d$ ) concomitante es la misma que una específica $G$ -equivariante de su modelo favorito para la representación irreducible $\lambda$ a ${\rm Sym}^d({\rm Sym}^n(V))$ (Grochow lo denomina módulo de separación ). Los teóricos de invariantes del siglo XIX disponían de dos métodos para generar tales objetos: la teoría de la eliminación y álgebra diagramática .
Un ejemplo muy bebé en el que $F_1$ y $F_2$ son formas cuárticas binarias bajo la acción de $G=SL(2)$ (véase esta pregunta del modus operandi ) es decir $$ F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4 $$ y $$ F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ . $$ Una concomitante separadora (aquí de hecho una covariante) es la hessiana de un cuártico binario genérico $F$ $$ H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ . $$ Desaparece (idénticamente en $x,y$ ) para $F=F_1$ pero no para $F=F_2$ . En este caso, el hessiano puede verse como un mapa equivariante que forma el irreducible dado por la segunda potencia simétrica (de la representación bidimensional fundamental) en el anillo de coordenadas del espacio afín de los cuárticos binarios.
Así pues, un posible "plan" superoptimista para GCT implica la siguiente secuencia de pasos.
Encuentra la forma de generar toneladas de concomitantes.
Identifique algunos candidatos explícitos para la desaparición en $F_1$ y demostrar esa propiedad.
Demuestra que no desaparecen en $F_2$ .
El paso 1) se resuelve en principio mediante la Primer teorema fundamental para $GL(n^2)$ pero hay un desajuste: el determinante es un objeto natural en la teoría invariante para $GL(n)\times GL(n)$ (que actúa sobre filas y columnas) en lugar de $GL(n^2)$ . Se podría intentar reparar el desajuste expresando el bloque de construcción básico para la teoría invariante de $GL(n^2)$ en términos de la de $GL(n)\times GL(n)$ (véase esta pregunta del modus operandi para un problema similar de reducción de $SL(n(n+1)/2)$ a $SL(n)$ ).
Adivinar los candidatos adecuados para el paso 2) me parece difícil. Sabiendo de antemano que algunas multiplicidades ${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$ son distintos de cero sería de gran ayuda. Aunque se podría aplazar la prueba de la desaparición no idéntica de la concomitante hasta el Paso 3), que de todas formas debería demostrar más que eso. Si uno tiene tales candidatos correctos, mostrando que desaparecen en $F_1$ puede ser fácil por argumentos que podríamos llamar el principio de exclusión de Pauli (contrayendo simetrizaciones con antisimetrizaciones), propiedad de alto número cromático, o simplemente "falta de espacio".
Sin embargo, creo que la parte más difícil es el paso 3). Por ejemplo, en mi documento "16.051 fórmulas para el invariante de Ottaviani de los trespliegues cúbicos" con Ikenmeyer y Royle, la búsqueda se hacía por ordenador, pero con el candidato adecuado en la mano, la desaparición en $F_1$ era relativamente fácil de explicar (es un ejemplo bastante bonito de número cromático debido a las propiedades globales del grafo y no a una gran camarilla). El análogo del paso 3) de nuestro artículo se hizo mediante cálculos informáticos de fuerza bruta y aún no tenemos ni idea de por qué es cierto. El problema paradigmático relacionado con el Paso 3) es el Conjetura de Alon-Tarsi (véase esta pregunta del modus operandi y éste también). En mi opinión, hay que avanzar en ese tipo de cuestiones (la Teorema de los cuatro colores también es de este tipo, mediante una reducción debida a Kauffman y Bar-Natan) antes de la conjetura de Valiant.
Dado que la pregunta se refiere a los avances en GCT. Creo que este artículo de Landsberg y Ressayre también merece cierta atención, ya que sugiere que una estimación razonable del valor exacto de $c(m)$ es $$ \left(\begin{array}{c}2m\\ m \end{array}\right)-1\ . $$ Obsérvese que una prueba de concepto para el enfoque explícito del "Paso 1),2),3)", en un problema mucho más sencillo, fue dada por Bürgisser e Ikenmeyer en este artículo . Por último, para más información sobre GCT, recomiendo encarecidamente la reseña "Teoría de la complejidad geométrica: una introducción para geómetras" por Landsberg.
PS: Debo añadir que mi pesimismo es específico de la Hipótesis Valiente, que es la "Hipótesis de Riemann" en este campo. Por supuesto, no hay que echar las campanas al vuelo y denigrar la GCT porque hasta ahora no haya podido demostrar esta conjetura. Hay muchos problemas más abordables en este campo en los que se ha avanzado y se espera que se siga avanzando. Véase, en particular, el artículo de Grochow y la reseña de Landsberg antes mencionados.
No puedo abordar los "avances actuales". Así que me limitaré a enumerar tres trabajos recientes. El primero es el resumen de Ketan Mulmuley sobre el programa CGT:
(1) Mulmuley, Ketan D. "El programa GCT hacia el problema P vs. NP". Comunicaciones de la ACM , 55.6 (2012): 98-107. Descargar PDF .
A continuación, el artículo que acaba de publicar Ketan, el quinto de una serie:
(2) Mulmuley, Ketan. "Teoría de la complejidad geométrica V: Algoritmos eficientes para la normalización de Noether". Revista de la Sociedad Matemática Americana , 30.1 (2017): 225-309. Versión arXiv anterior .
En el documento anterior, KM demuestra que Lemma de normalización de Noether (NNL) no es tan intratable como podría parecer (de la teoría de la base de Gröbner-exponencial en $n$ ). Demuestra que, "en la práctica, NNL para variedades explícitas puede resolverse eficientemente y correctamente con una alta probabilidad". La siguiente cuestión es lograr un tiempo polinómico determinista. Aquí sólo lo consigue parcialmente, mostrando que "para algunos casos interesantes de variedades explícitas," NNL "puede resolverse de forma determinista en tiempo casi polinomial". $(n)$ -tiempo". Esto trae algunos casos de NNL "de EXPSPACE a cuasi-P, asumiendo la hipótesis de dureza para la permanente en la teoría de la complejidad geométrica".
Y aquí hay una publicación bastante reciente en el arXiv, comentando "cómo [la] barrera de pruebas naturales algebraicas [que detallan] en la teoría de la complejidad geométrica":
(3) Grochow, J. A., Kumar, M., Saks, M., & Saraf, S. (2017). Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv:1701.01717 Resumen .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
