Incertidumbres en el programa GCT

En https://en.wikipedia.org/wiki/Geometric_complexity_theory se menciona que ".. Ketan Mulmuley cree que el programa, si es viable, es probable que tome alrededor de 100 años antes de que pueda resolver el problema P vs. NP".

Parece indicar que el único programa actualmente viable podría enfrentar serios obstáculos.

¿Cuáles son algunos de los obstáculos donde el programa podría fallar?

Depende de lo que cuentes como "el programa GCT".

1. Considere la sugerencia específica ( GCT I , GCT II ) de usar la desaparición / no desaparición de ciertas multiplicidades en los cierres de órbita del determinante y permanente para resolver la conjetura fuerte permanente versus determinante (es decir, que el permanente no está en el cierre de la órbita de cualquier determinante polinomialmente mayor). En este caso, es posible que incluso si la conjetura es cierta, que esto no se refleje en la desaparición / no desaparición de multiplicidades de irreps soportadas en estos cierres de órbita. Incluso es posible que la conjetura no se refleje en la desigualdad apropiada de multiplicidades. Debo señalar que hay varias formas de evidencia de que esto no debería suceder, pero aún no se ha descartado formalmente.

Sin embargo, tenga en cuenta que si en lugar de multiplicidades simplemente desea un módulo de separación , entonces la conjetura fuerte perm v det es verdadera si y solo si existe un módulo de separación.

2. Si su objetivo es la conjetura original permanente versus determinante, hay un paso anterior en GCT, a saber (como lo señala chazisop) pasar a la conjetura fuerte perm v det considerando los cierres de órbita . Es concebible que la conjetura original permanente versus determinante sea verdadera, pero la versión fuerte es falsa. Sin embargo, esto me parece muy poco probable. Además, si esta es la situación, ninguno de nuestros métodos actuales puede acercarse a resolver la conjetura perm v det, ya que todos trabajan actualmente para la versión "fuerte" / "aproximada" / "frontera -" / Zariski-cerrado de cualquier declaración de complejidad algebraica que estén demostrando.

3. $\mathsf{NP} \not\subseteq \mathsf{P/poly}$

4. [Fallos potenciales de los límites inferiores en general, no específicos de GCT.] GCT actualmente está dirigido a límites inferiores no uniformes; es decir, incluso en el enfoque GCT de los límites inferiores booleanos, está dirigido a mostrar . Pero, por supuesto, es consistente con los teoremas actuales que todavía . ¡Por supuesto, también es técnicamente posible que y la conjetura per v v det sea falsa!$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP} \subseteq \mathsf{P/poly}$$\mathsf{P} = \mathsf{NP}$

Sin embargo, permítanme señalar que el programa GCT tal como existe actualmente todavía me parece lo primero que debo probar . Si resulta que cualquiera de (1) - (3) arriba en realidad no funciona, significará que la conjetura per v v det (y por lo tanto, versus ) es casi inimaginable más difícil de lo que actualmente creemos que es. (Vale la pena señalar que esta declaración proviene de alguien que ya piensa que la siguiente analogía puede ser más o menos correcta, si no inadecuada: es para nuestro estado actual de conocimiento como el La clasificación de grupos simples finitos es para el pequeño teorema de Fermat ). E incluso si ese es el caso,$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$Comprender la forma exacta en que ocurre la falla probablemente será importante para seguir avanzando .

Creo que la declaración de "100 años" se refiere a que la teoría es general, pero requiere una comprensión profunda y nuevos resultados en la teoría de la representación y la geometría algebraica para progresar, algo que podría tardar en progresar (quiero hacer una comparación con la teoría de números, pero No estoy seguro de cuán apto es).

Además, hay una pérdida de precisión al traducir al mundo algebro-geométrico: en lugar de probar un límite inferior frente a las propiedades de una clase de complejidad (es decir, polinomios que desaparecen cuando los objetos de esa clase se dan como entrada), lo está probando. contra su cierre Zariski (de los polinomios mencionados anteriormente). Es concebible que para separar los dos, uno tenga que examinar el límite de ese cierre (aquellos polinomios que ocurren solo en el cierre pero en el conjunto original). Se cree que en la variante determinante vs permanente del programa GCT, este es probablemente el caso .

Finalmente, por experiencia personal, el conjunto de habilidades requeridas para comprender GCT en profundidad es bastante diferente de lo que generalmente es el enfoque de los programas de pregrado o incluso máster en CS, esencialmente recoger los requisitos previos es un seguimiento natural de elegir estudiar GCT.