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, ya sea P = NP , mostrando que la clase de complejidad P no es igual a la clase de complejidad NP .
La idea detrás del 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 probar los límites inferiores de los problemas. Actualmente, el enfoque principal del programa son las clases de complejidad algebraica . Se considera un hito importante para el programa demostrar que la computación de lo permanente no se puede reducir de manera eficiente a la computación de determinantes . Estos problemas de cálculo se pueden caracterizar por sus simetrías . El programa tiene como objetivo utilizar estas simetrías para demostrar límites inferiores.
Algunos consideran que el enfoque es el único programa viable actualmente activo para separar P de 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 de P vs. NP . [1]
El programa es llevado a cabo por varios investigadores en matemáticas e informática teórica. Parte de la razón 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 al P vs. NP y problemas relacionados. SIAM J. Comput. 31 (2), 496–526, 2001.
KD Mulmuley y M. Sohoni. Teoría de la Complejidad Geométrica II: Hacia Obstrucciones Explícitas para Incrustaciones entre Variedades de Clase. SIAM J. Comput., 38 (3), 1175–1206, 2008.