Explicación estilo Wikipedia de la teoría de la complejidad geométrica

¿Alguien puede proporcionar una explicación concisa del enfoque GCT de Mulmuley comprensible para los no expertos? Una explicación que sería adecuada para una página de Wikipedia sobre el tema (que es un trozo en este momento).

Motivación: estoy "co-leyendo" el libro de computación cuántica de Scott Aaronson desde Demócrito con un amigo mío que es investigador en teoría de cuerdas. En el prefacio del libro, Aaronson llama a GCT "la teoría de cuerdas de la informática". Siendo un teórico de cuerdas, mi amigo se entusiasmó con este reclamo y me preguntó qué es GCT. En ese momento me di cuenta vergonzosamente que no tenía una respuesta lista para Wikipedia para su pregunta.

No estoy exactamente seguro de qué nivel es adecuado para el artículo de Wikipedia (diferentes artículos parecen estar dirigidos a diferentes niveles de experiencia) o exactamente lo que está buscando. Así que aquí hay una oportunidad, pero estoy abierto a comentarios.

La teoría de la complejidad geométrica propone estudiar la complejidad computacional de las funciones informáticas (por ejemplo, polinomios) explotando las simetrías inherentes en la complejidad y cualquier simetría adicional de las funciones que se estudian.

Al igual que con muchos enfoques anteriores, el objetivo final es para separar dos clases de complejidad , mostrando que hay un polinomio p que realiza funciones f como entradas (digamos, por sus vectores de coeficientes) de manera que p desaparece en cada función f ∈ C e a s y no desaparece en alguna función g h a r d ∈ C h a r d .$\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

La primera idea clave (cf. [GCT1, GCT2]) es usar simetrías para organizar no las funciones en sí mismas, sino para organizar las propiedades ( algebro-geométricas ) de estas funciones, capturadas por polinomios como arriba. Esto permite el uso de la teoría de la representación al intentar encontrar tal p . Ideas similares relacionadas con la teoría de la representación y la geometría algebraica se habían utilizado antes en geometría algebraica, pero que yo sepa, nunca de esta manera.$p$$p$

La segunda idea clave (cf. [GCT6]) es encontrar algoritmos combinatorios (y de tiempo polinómico) para los problemas teóricos de representación resultantes, y luego aplicar ingeniería inversa a estos algoritmos para mostrar que tal existe. Esto puede tomarse en el espíritu de usar la Programación Lineal (un algoritmo) para probar ciertas declaraciones puramente combinatorias.$p$

De hecho, [GCT6] sugiere reducir los problemas teóricos de representación anteriores a problemas de Programación de enteros , luego mostrar que las IP resultantes se resuelven por sus relajaciones de LP y finalmente dar algoritmos combinatorios para los LP resultantes. Las conjeturas en [GCT6] están motivadas por resultados conocidos de ingeniería inversa para los coeficientes de Littlewood-Richardson, un problema análogo pero más fácil en la teoría de la representación. En el caso de los coeficientes LR, la regla combinatoria de Littlewood-Richardson fue lo primero. Más tarde, Berenstein y Zelevinsky [BZ] y Knutson y Tao [KT] (ver [KT2] para una descripción amistosa) dieron una IP para los coeficientes LR. Knutson y Tao también demostraron la conjetura de saturación, lo que implica que el IP se resuelve con su relajación LP (cf. [GCT3, BI]).

Los resultados de [GCT5] muestran que desrandomizar explícitamente el Lema de normalización de Noether es esencialmente equivalente al notorio problema abierto en la teoría de la complejidad de la desrandomización de recuadro negro de las pruebas de identidad polinomiales . Aproximadamente cómo encaja esto en el programa más amplio es que encontrar una base explícita para las funciones que (no) desaparecen en C e a s y (en este caso, la clase para la cual el determinante está completo) podría usarse para derivar un regla combinatoria para el problema deseado en la teoría de la representación, como ha sucedido en otros entornos en geometría algebraica. Un paso intermedio aquí sería encontrar una base para esos $p$$\mathcal{C}_{easy}$$p$que (no) se desvanecen en la normalización de , que es por construcción una variedad algebraica más agradable, en otras palabras, desrandomizar el Lema de Normalización de Noether para DET.$\mathcal{C}_{easy}$

Ejemplos de simetrías de complejidad y funciones.

Por ejemplo, la complejidad de una función , para la mayoría de las nociones naturales de complejidad, no cambia si permutamos las variables f ( x π ( 1 ) , ... , x π ( n ) ) por alguna permutación π . Así, las permutaciones son simetrías de la complejidad misma. Para algunas nociones de complejidad (como en la complejidad del circuito algebraico) todos los cambios lineales invertibles de las variables son simetrías.$f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

det ( A X B ) = det ( X T ) = det ( X ) A , B det ( A B ) = $\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Algunos avances recientes [esta sección definitivamente está incompleta y es más técnica, pero una cuenta completa tomaría decenas de páginas ... solo quería resaltar algunos avances recientes]

Burgisser e Ikenmeyer [BI2] mostraron un límite inferior en la multiplicación de matrices siguiendo el programa GCT en cuanto a usar representaciones con multiplicidades cero vs no cero. Landsberg y Ottaviani [LO] dieron el límite inferior más conocido de esencialmente en el rango del borde de la multiplicación de matrices usando la teoría de la representación para organizar las propiedades algebraicas, pero no usando multiplicidades de representación ni reglas combinatorias.2n$\frac{3}{2}n^2$$2n^2$

El siguiente problema después de los coeficientes de Littlewood-Richardson son los coeficientes de Kronecker . Estos aparecen tanto en una serie de problemas que se sospecha que eventualmente alcanzarán los problemas teóricos de representación que surgen en GCT, y más directamente como límites en las multiplicidades en el enfoque de GCT para la multiplicación de matrices y permanente versus determinante. Encontrar una regla combinatoria para los coeficientes de Kronecker es un problema abierto de larga data en la teoría de la representación; Blasiak [B] recientemente dio una regla combinatoria para los coeficientes de Kronecker con una forma de gancho.

Kumar [K] mostró que ciertas representaciones aparecen en el anillo de coordenadas del determinante con multiplicidad distinta de cero, asumiendo la conjetura del cuadrado latino de la columna (cf. Huang-Rota y Alon-Tarsi; esta conjetura también, tal vez no casualmente, aparece en [BI2 ]). Por lo tanto, estas representaciones no pueden usarse para separar lo permanente de lo determinante sobre la base de multiplicidades cero frente a cero, aunque aún podría ser posible usarlas para separar lo permanente de lo determinante por una desigualdad más general entre multiplicidades.

Referencias [B] J. Blasiak. Coeficientes de Kronecker para una forma de gancho. arXiv: 1209.2018, 2012.

[BI] P. Burgisser y C. Ikenmeyer. Un algoritmo de flujo máximo para la positividad de los coeficientes de Littlewood-Richardson. FPSAC 2009.

[BI2] P. Burgisser y C. Ikenmeyer. Límites inferiores explícitos a través de la teoría de la complejidad geométrica. arXiv: 1210.8368, 2012.

[BZ] AD Berenstein y AV Zelevinsky. Multiplicidades triples para y el espectro del álgebra exterior de la representación adjunta. $\mathfrak{sl}(r+1)$J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] KD Mulmuley y M. Sohoni. Teoría de la complejidad geométrica I: un enfoque de la P vs. NP y problemas relacionados. SIAM J. Comput. 31 (2), 496-526, 2001.

[GCT2] KD Mulmuley y M. Sohoni. Teoría de la complejidad geométrica II: hacia obstrucciones explícitas para incrustaciones entre variedades de clase. SIAM J. Comput., 38 (3), 1175-1206, 2008.

[GCT3] KD Mulmuley, H. Narayanan y M. Sohoni. Teoría de la complejidad geométrica III: sobre la decisión de no desvanecimiento de un coeficiente de Littlewood-Richardson. J. Algebraic Combin. 36 (2012), no. 1, 103-110.

[GCT5] KD Mulmuley. Teoría de la Complejidad Geométrica V: Equivalencia entre la desrandomización de caja negra de las pruebas de identidad polinomial y la desleatización del Lemma de Normalización de Noether. FOCS 2012, también arXiv: 1209.5993.

[GCT6] KD Mulmuley. Teoría de la complejidad geométrica VI: el cambio a través de la positividad. , Informe técnico, departamento de informática, Universidad de Chicago, enero de 2011.

[K] S. Kumar. Un estudio de las representaciones respaldadas por el cierre de la órbita del determinante. arXiv: 1109.5996, 2011.

[LO] JM Landsberg y G. Ottaviani. Nuevos límites inferiores para el rango de borde de la multiplicación de matrices. arXiv: 1112.6007, 2011.

[KT] A. Knutson y T. Tao. El modelo de panal de los productos tensoriales . I. Prueba de la conjetura de saturación. $\text{GL}_n(\mathbb{C})$J. Amer. Mates. Soc. 12 (1999), no. 4, 1055-1090.

[KT2] A. Knutson y T. Tao. Panales y sumas de matrices hermitianas. Avisos Amer. Mates. Soc. 48 (2001), no. 2, 175-186.

Recientemente di una respuesta a una pregunta relacionada sobre Mathoverflow https://mathoverflow.net/questions/277408/what-are-the-current-breakthroughs-of-geometric-complexity-theory

Dado que este sitio es quizás un mejor lugar, permítanme repetir esa respuesta a continuación. Las referencias a Joseph o Timothy son sobre las otras publicaciones para esa pregunta de MO.

---

Sea una matriz genérica y el grado polinomio homogéneo dado por El determinante. Deje que toma el permanente de una submatriz y se multiplica por la forma lineal favorita de uno para hacer otro polinomio homogéneo de grado (también se puede usar la entrada lugar de ). Esta modificación se llama relleno . Luego define el número n × n F 1 ( X ) = d e t ( X ) n F 2 ( X ) = ( X n n ) n - m × p e r m [ ( X i j ) 1 ≤ i , j $X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$ m×mnX 11 X n n c(m)=min{n| n≥mand ¯ G ⋅ F 2 ⊂ ¯ G ⋅ F 1 }GGL(n2)n2X ¯ G ⋅ F i P≠NPc(m

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ donde es actuando en el espacio afín de la dimensión donde vive y son cierres de órbitas de Zariski. La gran conjetura en el área o la hipótesis de Valiant (una versión compleja de ) es que crece más rápido que cualquier polinomio en .$G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

Ahora si , entonces uno tiene un mapa equivalente equivalente entre grados partes de los anillos de coordenadas de estos cierres de órbita. Entonces, el juego es tratar de demostrar que esto no sucede, para insuficientemente grande en relación con , probando la existencia de una obstrucción de multiplicidad , es decir, una representación irreducible para la cual las multiplicidades satisfacen $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ o al nivel de 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 tratar de mostrar que existen obstrucciones de ocurrencia , es decir, 's tal que y . Esta esperanza ha sido aplastada en el trabajo de Bürgisser, Ikenmeyer y Panova mencionado por Timothy. Sin embargo, la posibilidad de obstrucciones por multiplicidad aún está abierta.$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$

Creo que el enfoque de Mulmuley es tratar de probar 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 he sido fanático de este enfoque. Habiendo estudiado la teoría invariante del siglo XIX con cierta profundidad, me parece más natural abordar el problema de separación de la órbita utilizando las herramientas explícitas de esa época. Este artículo de Gorchow parece apuntar también en una dirección similar (sospecho que el tercer artículo mencionado por Joseph está en la misma línea). En lenguaje clásico (ver Turnbull o Littlewood ), uno tiene que construir explícitamente un concomitante mixto que desaparezca en$F_1$pero no en . También hay que hacer esto infinitamente a menudo (en ) para establecer la propiedad de crecimiento superpolinomial. Tal concomitante es lo mismo que un mapa equivalente equivalente de su modelo favorito para la representación irreducible al álgebra polinomial en las variables (Grochow llama a eso un módulo de separación ). Los teóricos invariantes del siglo XIX tenían dos métodos para generar tales objetos: la teoría de la eliminación y el álgebra esquemática .$F_2$$m$$G$$\lambda$$n^2$$X$

Un ejemplo muy pequeño en el que y son formas binarias bajo la acción de (vea esta pregunta de MO ) es decir y Un concomitante separador (aquí, de hecho, una covariante) es el hessiano de un cuarto binario genérico Se desvanece (idénticamente en ) para pero no para$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $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\ .$$ $x,y$$F=F_1$$F=F_2$. En este caso, el hessiano puede verse como un mapa equivalente del irreducible dado por la segunda potencia simétrica (de la representación bidimensional fundamental) en el anillo de coordenadas para el espacio afín de los cuartos binarios.

Por lo tanto, un posible "plan" superoptimista para GCT implica la siguiente secuencia de pasos.

1) Encuentre una manera de generar toneladas de concomitantes.

2) Identifique algunos candidatos explícitos para la desaparición en y pruebe esa propiedad.$F_1$

3) Mostrar que no desaparecen en .$F_2$

El paso 1) se resuelve en principio mediante el primer teorema fundamental para pero hay un desajuste: el determinante es un objeto natural en la teoría invariante de (que actúa en filas y columnas) en lugar de . Se podría tratar de reparar el desajuste expresando el bloque de construcción básico para la teoría invariante de en términos de la de (vea esta pregunta de MO para un problema de reducción similar desde a ).$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

Adivinar los candidatos correctos para el Paso 2) me parece difícil. Saber de antemano que algunas multiplicidades definitivamente no ayudarían. Sin embargo, uno podría postergar y diferir la prueba de desaparición no idéntica del concomitante al Paso 3), que de todos modos debería mostrar más que eso. Si uno tiene esos candidatos correctos, demostrar que se desvanecen en puede ser fácil con argumentos que se podría llamar el principio de exclusión de Pauli (contracción de simetrizaciones con antisimmetrizaciones), propiedad de alto número cromático o simplemente `` falta de espacio ''. F ${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

Sin embargo, creo que la parte más difícil es el Paso 3). Por ejemplo, en mi artículo "16,051 fórmulas para la invariante de las tres capas cúbicas de Ottaviani" con Ikenmeyer y Royle, la suposición se realizó mediante búsqueda por computadora, pero con el candidato adecuado en la mano, la desaparición en fue relativamente fácil de explicar (es bastante bonito ejemplo de número cromático debido a las propiedades globales del gráfico en lugar de una gran camarilla). El análogo del Paso 3) en nuestro artículo se realizó mediante cálculo por computadora de fuerza bruta y todavía no tenemos idea de por qué es cierto. El problema paradigmático relacionado con el Paso 3) es la conjetura de Alon-Tarsi (vea esta pregunta de MO y esta)$F_1$también). En mi opinión, uno necesita avanzar en ese tipo de preguntas (el Teorema de los cuatro colores también es de este tipo, a través de una reducción debida a Kauffman y Bar-Natan) antes de la Conjetura de Valiant.

Dado que la pregunta es sobre avances en GCT. Creo que este artículo de Landsberg y Ressayre también merece cierta atención, ya que sugiere que una suposición razonable para el valor exacto de es Tenga en cuenta que Bürgisser e Ikenmeyer dieron una prueba de concepto para el enfoque explícito "Paso 1), 2), 3)", sobre un problema mucho más simple, en este artículo . Finalmente, para obtener más información sobre GCT, recomiendo encarecidamente la revisión "Teoría de la complejidad geométrica: una introducción para los geómetras" de Landsberg.( 2 m m ) - 1 $c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PD: Debo agregar que mi pesimismo es específico de la Hipótesis Valiente, que es la 'Hipótesis de Riemann' en el campo. Por supuesto, uno no debe tirar al bebé con el agua del baño y denigrar el GCT porque hasta ahora no pudo probar esta conjetura. Hay muchos más problemas abordables en esta área donde se han realizado progresos y se espera más progreso. Ver en particular el artículo mencionado anteriormente por Grochow y la revisión de Landsberg.

GCT es un programa de investigación para probar los límites de la teoría de la complejidad y, en cierto modo, desafía un resumen / resumen estilo wikipedia debido a su gran abstracción, pero para la multitud de TCS hay buenas encuestas disponibles. [2] [3] [4] (y seguramente Wikipedia es el mejor lugar para las entradas de wikipedia). fue formulado a principios de la década de 2000 por Mulmuley y es relativamente nuevo en teoría de la complejidad y muy avanzado, utilizando y aplicando matemáticas avanzadas (geometría algebraica) que no se originaron en TCS / teoría de la complejidad.

el enfoque es considerado prometedor por algunas, pero posiblemente demasiado complejo por otras autoridades, es decir, no está probado y, por lo tanto, es controvertido si podría superar las "barreras" estándar conocidas. (en este sentido, exhibe algunos signos de un llamado "cambio de paradigma" kuhniano). incluso Mulmuley propone que de manera realista podría no tener éxito (al demostrar separaciones de clase de mayor complejidad) después de décadas de desarrollo adicional. Aquí hay una opinión escéptica de Fortnow, una autoridad líder en el campo de la teoría de la complejidad: [1]

Considera una montaña enorme y quieres llegar a la cima de la montaña. Ketan aparece y dice que le enseñará cómo crear las herramientas necesarias para escalar la montaña. Tomará un mes duro de estudio y, en realidad, estas herramientas no son lo suficientemente buenas para escalar la montaña. Deben mejorarse y estas mejoras no sucederán en su vida. ¿Pero no quieres aprender cómo otros escalarán la montaña dentro de siglos?

[1] Cómo demostrar que NP es diferente al blog de P Fortnow

[2] Comprensión del enfoque de Mulmuley-Sohoni para P vs. NP Regan

[3] Sobre P vs. NP y teoría de la complejidad geométrica Mulmuley

[4] El programa GCT hacia el problema P vs. NP Mulmuley