Programa GCT de Mulmuley

38

A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el programa. Según Mulmuley, llevará mucho tiempo lograr los resultados deseados. Entrar en el área no es fácil para los teóricos de la complejidad general y necesita esfuerzos considerables para manejar la geometría algebraica y la teoría de la representación.

  1. ¿Por qué se considera que GCT es capaz de resolver P vs. NP? ¿Cuál es el valor del reclamo si se espera que tarde más de 100 años en llegar allí? ¿Cuáles son sus ventajas para otros enfoques actuales y aquellos que pueden aumentar en los próximos 100 años?

  2. ¿Cuál es el estado actual del programa?

  3. ¿Cuál es el próximo objetivo del programa?

  4. ¿Ha habido alguna crítica fundamental al programa?

Preferiría respuestas que sean entendibles por un teórico de la complejidad general con el mínimo conocimiento de geometría algebraica y teoría de la representación asumida.

Anónimo
fuente
12
¿Vio el tutorial de Mulmuley en FOCS (disponible en techtalks.tv/talks/1301 ) y leyó la exposición de Ken Regan: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Mulmuley definitivamente dio su intuición de por qué cree que su programa es viable (y creo que argumenta que es necesario hasta cierto punto), y también por qué es difícil.
Sasho Nikolov
55
Publicaciones de blog relacionadas: 1 , 2 . Scott también escribe: "El programa GCT de Mulmuley es el único enfoque para P vs. NP que he visto que incluso tiene aspiraciones serias de" conocer "muchas técnicas no triviales para resolver problemas en P (al menos, programación coincidente y lineal) Para mí, ese es probablemente el argumento más fuerte a favor de GCT ".
Kaveh
77
Creo que GCT apunta a VP vs VNP y no P vs NP.
Iddo Tzameret
66
@ Iddo: En realidad, puede estar dirigido a muchas cosas (más de lo que está dirigido actualmente). Para "perm v det sobre " está dirigido a ¯ V P w s vs V N P (ver arxiv.org/abs/0907.2850 ). Sin embargo, en campos finitos y para funciones distintas de perm y det, puede apuntar directamente a P vs NP. doVPAGSws¯VnortePAGS
Joshua Grochow
44
@Mohammad: El hecho de que una solución sea inesperada y requiera ideas completamente nuevas no significa que no sea así. De hecho, muchos ya creen que resolver P vs NP por cualquier método requerirá ideas completamente nuevas ...
Joshua Grochow

Respuestas:

23

Como lo señalaron muchos otros, Mulmuley, Regan y otros ya han dicho mucho sobre muchas de estas preguntas. Ofreceré aquí solo un breve resumen de lo que creo que son algunos puntos clave que aún no se han mencionado en los comentarios.

  1. En cuanto a por qué GCT se considera plausiblemente capaz de mostrar ya se han dado muchas respuestas en otros lugares y en los comentarios anteriores, aunque creo que nadie ha mencionado aún que parece evitar las barreras conocidas (relativización, algebrización, pruebas naturales ) En cuanto a su valor, creo que incluso si nos lleva 100 años, aprenderemos algo nuevo sobre la complejidad en el camino al estudiarlo desde este ángulo.PAGSnortePAGS

    • Se está progresando en la comprensión de las variedades algebraicas, las representaciones y las preguntas algorítmicas que surgen en GCT. Los principales investigadores que conozco que han trabajado en esto son (sin ningún orden en particular): P. Burgisser, C. Ikenmeyer, M. Christandl, JM Landsberg, KV Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar y, por supuesto, K. Mulmuley y M. Sohoni.

    • Más concretamente, Burgisser e Ikenmeyer acaban de presentar (STOC 2011) algunos límites inferiores modestos en la multiplicación de matrices utilizando el enfoque GCT ( , en comparación con los 3 más conocidos actualmentenorte2+232norte2+O(norte)

    • N. Kayal tiene un par de documentos sobre la cuestión algorítmica de las pruebas cuando un polinomio está en la órbita de otro o es una proyección de otro. Él muestra que, en general, estos problemas son NP-hard pero que para funciones especiales como polinomios simétricos permanentes, determinantes y elementales, estos problemas son decidibles en P. Este es un paso hacia algunas de las conjeturas de Mulmuley (que ciertos problemas más difíciles: decidir la órbita cierre - están en P para funciones especiales como determinante).

  2. No tengo mucho más específico que decir sobre esto que la respuesta a 2.

  3. Hasta donde sé, no ha habido críticas fundamentales , en el sentido de que no he visto ninguna crítica que realmente desacredite al programa de ninguna manera. Ciertamente se ha debatido sobre por qué deberían ser necesarias tales técnicas, el valor del programa dados los horizontes esperados a largo plazo, etc., pero yo los caracterizaría más como una discusión saludable que como una crítica fundamental.

Joshua Grochow
fuente
1
@ user124864: en principio sí. GCT es solo un enfoque para mostrar los límites inferiores, cualesquiera que sean esos límites inferiores. Parece que debería funcionar mejor para funciones caracterizadas por sus simetrías, pero esta última propiedad no depende del valor numérico del límite inferior que desea mostrar (por ejemplo, cuasipoly vs exp).
Joshua Grochow