¿Qué tan difícil es usar el enfoque de GCT de Mulmuley-Sohoni para mostrar separaciones de complejidad * conocidas *?

31

En esta publicación invitada de Josh Grochow en el complejo weblog, informa sobre un taller reciente dedicado a GCT que se celebró en Princeton en julio. Varios de los asistentes argumentaron que deberíamos usar GCT para atacar problemas más fáciles que vs. N P para construir la intuición y ver si el método tiene potencial.PNP

La pregunta que me ha estado molestando:

¿Es posible usar GCT para mostrar separaciones conocidas como o LP S P A C E ?PEXPLPSPACE

Hace algo como LPSPACE

  1. Ni siquiera tiene sentido en el contexto GCT, o
  2. Es completamente trivial y poco interesante en el marco de GCT, o
  3. ¿Llevar a conjeturas tan difíciles como vs. N P ?PNP
Mugizi Rwebangira
fuente
Los comentarios de Josh sobre esa publicación parecen implicar que ES posible formular tal separación en "lenguaje GCT", pero no es trivial y nadie ha podido hacerlo todavía. Pero aún así agradecería cualquier idea de un experto.
Mugizi Rwebangira
44
AFAIR, Mulmuley comienza su presentación ( video.ias.edu/stream&ref=226 ) con #P vs NC como una pregunta más natural para GCT. Esta puede ser una primera intuición para responder a su pregunta.
Michaël Cadilhac
Gracias por ese enlace Michaël. Por alguna razón, el volumen es demasiado bajo para que pueda escucharlo en el escritorio de mi oficina, pero lo intentaré cuando llegue a casa. Aunque en cualquier caso Josh ya ha dado una buena respuesta.
Mugizi Rwebangira

Respuestas:

25

Respuesta corta: probablemente no (1), definitivamente no (2), y posiblemente (3).

Esto es algo en lo que he estado pensando de vez en cuando. Primero, en cierto sentido, GCT está realmente destinado a dar límites más bajos a las funciones informáticas, en lugar de problemas de decisión. Pero su pregunta tiene mucho sentido para las versiones de clase de función de , P , PLP y E X P .PSPACEEXPAGS

En segundo lugar, probar las versiones booleanas, las que conocemos y amamos, como , es probablemente increíblemente difícil en un enfoque GCT, ya que eso requeriría el uso de la teoría de representación modular (teoría de representación sobre finita campos), que no se entiende bien en ningún contexto. FPAGSFmiXPAGS

Sin embargo, un objetivo razonable podría ser el uso de GCT para probar un análogo algebraica de .FPAGSFmiXPAGS

Para llegar a su pregunta: creo que estas preguntas pueden formularse en un contexto GCT, aunque no es obvio de inmediato cómo. Más o menos, necesita una función completa para la clase y caracterizada por sus simetrías; bonificación adicional si la teoría de representación asociada a la función es fácil de entender, pero esta última suele ser bastante difícil.

Incluso una vez que las preguntas se formulan en un contexto GCT, no tengo idea de lo difícil que será usar GCT para probar (análogos algebraicos de) etc. Las conjeturas teóricas de representación que surgirán en estos contextos probablemente tendrá un sabor muy similar a los que surgen en P vs N PFPFEXPPNPo permanente vs determinante. Uno podría esperar que las pruebas clásicas de estos resultados de separación den una idea de cómo encontrar las "obstrucciones" teóricas de la representación necesarias para una prueba GCT. Sin embargo, las pruebas de las afirmaciones que menciona son todos teoremas de jerarquía basados ​​en la diagonalización, y no veo cómo la diagonalización realmente le dará mucha información sobre la teoría de representación asociada con una función que está completa para (el análogo algebraico de) , por ejemplo. Por otro lado, todavía no he visto cómo formular F E X P en un contexto GCT, por lo que es un poco pronto para decirlo.FEXPFEXP

Finalmente, como mencioné en esa publicación de blog, Peter Burgisser y Christian Ikenmeyer han intentado volver a probar el límite inferior en el rango en el borde de la multiplicación de matriz (que Joseph Landsberg demostró que era 7 en 2006). Pudieron mostrar que el rango fronterizo es al menos 6 mediante una búsqueda por computadora de obstrucciones de GCT. Actualización de abril de 2013 : desde entonces han logrado volver a probar el resultado de Landsberg usando una obstrucción GCT y mostrar un asintótico 32×232n22

2×23×33×3FPFEXP , mientras que sabemos que la diagonalización no.PNPAGS

Joshua Grochow
fuente
99
Parece una locura que debería ser tan difícil para reprobar ! FPAGSFmiXPAGS
Ryan Williams
2
¡Gracias! Eso fue MUY útil. Mi idea general (y creo que también la de los demás) era pensar en lo que sería un "primer paso fácil" en este programa de GCT. Pero parece que realmente no hay uno (al menos hasta ahora). Usted mencionó que el enfoque de Grobner Bases tiene un tiempo de ejecución doblemente exponencial, ¿sabe cuál fue el tiempo de ejecución (asintótico) de la búsqueda que hicieron Burgisser e Ikenmeyer?
Mugizi Rwebangira
3
Creo que todavía estaba exponencial (que explica en parte por qué no podían reproducirse bastante resultado de Landsberg), pero sólo de forma simple exponencial :).
Joshua Grochow
1
@JoshuaGrochow: Sería útil si coloca un banner de actualización al principio o al final de la respuesta. En mi vejez, mis ojos ya no son lo que solían ser, y al leer la respuesta por primera vez, me perdí el cambio.
Vijay D
14

Hay un nuevo documento sobre el arXiv de Joshua Grochow , que muestra cómo poner varias técnicas conocidas de límite inferior en el marco de GCT y parece que responde a su pregunta de alguna manera.

(Esto es principalmente solo un comentario, pero nadie notaría un comentario, así que lo publico como respuesta).

Unificar y generalizar los límites inferiores conocidos a través de la teoría de la complejidad geométrica.

Joshua A. Grochow

AC0[p]por lo que es una unificación natural y una amplia generalización de resultados conocidos. También muestra que el marco de trabajo de GCT es al menos tan poderoso como los métodos conocidos, y ofrece muchas nuevas pruebas de concepto de que GCT puede proporcionar límites inferiores asintóticos significativos. Este nuevo punto de vista también abre la posibilidad de fructíferas interacciones bidireccionales entre los resultados anteriores y los nuevos métodos de GCT; Proporcionamos varias sugerencias concretas de tales interacciones. Por ejemplo, el punto de vista teórico de la representación de GCT proporciona naturalmente nuevas propiedades a considerar en la búsqueda de nuevos límites inferiores. Este nuevo punto de vista también abre la posibilidad de fructíferas interacciones bidireccionales entre los resultados anteriores y los nuevos métodos de GCT; Proporcionamos varias sugerencias concretas de tales interacciones. Por ejemplo, el punto de vista teórico de la representación de GCT proporciona naturalmente nuevas propiedades a considerar en la búsqueda de nuevos límites inferiores. Este nuevo punto de vista también abre la posibilidad de fructíferas interacciones bidireccionales entre los resultados anteriores y los nuevos métodos de GCT; Proporcionamos varias sugerencias concretas de tales interacciones. Por ejemplo, el punto de vista teórico de la representación de GCT proporciona naturalmente nuevas propiedades a considerar en la búsqueda de nuevos límites inferiores.

Robin Kothari
fuente