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.
La pregunta que me ha estado molestando:
¿Es posible usar GCT para mostrar separaciones conocidas como o L ≠ P S P A C E ?
Hace algo como
- Ni siquiera tiene sentido en el contexto GCT, o
- Es completamente trivial y poco interesante en el marco de GCT, o
- ¿Llevar a conjeturas tan difíciles como vs. N P ?
cc.complexity-theory
gct
Mugizi Rwebangira
fuente
fuente
Respuestas:
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 , PL P y E X P .PSPACE EXP
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.FPAGS≠ FmiXPAGS
Sin embargo, un objetivo razonable podría ser el uso de GCT para probar un análogo algebraica de .FPAGS≠ FmiXPAGS
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 PFP≠FEXP P NP o 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.FEXP FEXP
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×2 32n2−2
fuente
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).
fuente