La teoría de la complejidad geométrica (GCT) , es un programa de investigación en teoría de la complejidad computacional propuesto por Ketan Mulmuley y Milind Sohoni. El objetivo del programa es responder al problema abierto más famoso de la informática ( si P = NP ) demostrando que la clase de complejidad P no es igual a la clase de complejidad NP .
La idea detrás de este enfoque es adoptar y desarrollar herramientas avanzadas en geometría algebraica y teoría de la representación (es decir, teoría geométrica invariante ) para demostrar los límites inferiores de los problemas. Actualmente, el enfoque principal del programa son las clases de complejidad algebraica . Demostrar que calcular lo permanente no se puede reducir eficientemente a calcular los determinantes se considera un hito importante para el programa. Estos problemas computacionales se pueden caracterizar por sus simetrías . El programa tiene como objetivo utilizar estas simetrías para demostrar límites inferiores.
Algunos consideran que este enfoque es el único programa actualmente activo viable para separar el P del NP . Sin embargo, Ketan Mulmuley cree que el programa, si es viable, probablemente tardará unos 100 años antes de que pueda resolver el problema P versus NP . [1]
El programa es realizado por varios investigadores en matemáticas e informática teórica. Parte del motivo del interés en el programa es la existencia de argumentos para que el programa evite barreras conocidas como la relativización y las pruebas naturales para demostrar límites inferiores generales. [2]
KD Mulmuley y M. Sohoni. Teoría de la complejidad geométrica I: una aproximación a P vs. NP y problemas relacionados. SIAM J. Computación. 31(2), 496–526, 2001.
KD Mulmuley y M. Sohoni. Teoría de la complejidad geométrica II: hacia obstrucciones explícitas para las incrustaciones entre variedades de clases. SIAM J. Comput., 38(3), 1175–1206, 2008.
KD Mulmuley, H. Narayanan y M. Sohoni. Teoría de la complejidad geométrica III: sobre la decisión de no desaparecer de un coeficiente de Littlewood-Richardson. J. Combinación algebraica. 36 (2012), núm. 1, 103–110.
KD Mulmuley. Teoría de la Complejidad Geométrica V: Algoritmos eficientes para la normalización de Noether. J.Amer. Matemáticas. Soc. 30 (2017), núm. 1, 225-309. arXiv:1209.5993 [cs.CC]
KD Mulmuley. Teoría de la complejidad geométrica VI: el giro a través de la positividad. Informe técnico, departamento de Ciencias de la Computación, Universidad de Chicago, enero de 2011.