Hispanopedia WikiLa teoría de la complejidad geométrica (TCG) 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 resolver el 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 subyacente a este enfoque es adoptar y desarrollar herramientas avanzadas de geometría algebraica y teoría de la representación (es decir, teoría de invariantes geométricos ) para demostrar cotas inferiores en diversos problemas. Actualmente, el programa se centra en clases de complejidad algebraica . Demostrar que el cálculo del permanente no puede reducirse eficientemente al cálculo de determinantes se considera un hito importante. Estos problemas computacionales se caracterizan por sus simetrías . El programa busca utilizar estas simetrías para demostrar cotas inferiores.
Algunos consideran que este enfoque es el único programa viable actualmente en funcionamiento para separar P de NP . Sin embargo, Ketan Mulmuley cree que, de ser viable, el programa probablemente tardará unos 100 años en resolver el problema de P vs. NP . [ 1 ]
El programa es desarrollado por varios investigadores en matemáticas y ciencias de la computación teórica. Parte del interés en el programa radica en la existencia de argumentos que permiten evitar barreras conocidas como la relativización y demostraciones naturales para probar cotas inferiores generales. [ 2 ]
Referencias
- ↑ Fortnow, Lance (2009), "El estado del problema P versus NP", Communications of the ACM , 52 (9): 78–86 , CiteSeerX 10.1.1.156.767 , doi : 10.1145/1562164.1562186 , S2CID 5969255 .
- ↑ Mulmuley, Ketan D. (2011-04-01). "Sobre P vs. NP y la teoría de la complejidad geométrica: Dedicado a Sri Ramakrishna" . Journal of the ACM . 58 (2): 5. doi : 10.1145/1944345.1944346 . ISSN 0004-5411 . S2CID 7703175 .
Lecturas adicionales
- KD Mulmuley y M. Sohoni. Teoría de la complejidad geométrica I: Un enfoque para los problemas 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 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 determinación de la no anulación de un coeficiente de Littlewood-Richardson. J. Algebraic Combin. 36 (2012), n.º 1, 103–110.
- KD Mulmuley. Teoría de la complejidad geométrica V: Algoritmos eficientes para la normalización de Noether. J. Amer. Math. Soc. 30 (2017), n.º 1, 225-309. arXiv:1209.5993 [cs.CC]
- KD Mulmuley. Teoría de la complejidad geométrica VI: el cambio a través de la positividad., Informe técnico, Departamento de Ciencias de la Computación, Universidad de Chicago, enero de 2011.
Enlaces externos
- Página de GCT, Universidad de Chicago
- Descripción en la página web del Instituto Simons
- Preguntas de GCT sobre teoría de la computación
- Explicación al estilo de Wikipedia de la Teoría de la Complejidad Geométrica por Joshua Grochow
- ¿Cuáles son los avances más recientes en la Teoría de la Complejidad Geométrica?
- https://mathoverflow.net/questions/243011/why-should-algebraic-geometers-and-representation-theorists-care-about-geometric/
- Teoría de la complejidad computacional