A Teoria da Complexidade Geométrica (GCT) é um programa de pesquisa na teoria da complexidade computacional proposto por Ketan Mulmuley e Milind Sohoni. O objetivo do programa é responder ao problema em aberto mais famoso da ciência da computação – se P = NP – demonstrando que a classe de complexidade P não é igual à classe de complexidade NP.
A ideia por trás da abordagem é adotar e desenvolver ferramentas avançadas em geometria algébrica e teoria de representação (isto é, teoria geométrica dos invariantes) para provar limites inferiores (lower bounds) para problemas. Atualmente, o foco principal do programa está nas classes de complexidade algébrica. Provar que o cálculo do permanente não pode ser eficientemente reduzido ao cálculo de determinantes é considerado um grande marco para o programa. Esses problemas computacionais podem ser caracterizados por suas simetrias. O programa visa utilizar essas simetrias para provar limites inferiores.
A abordagem é considerada por alguns como o único programa atualmente ativo e viável para separar P de NP. No entanto, Ketan Mulmuley acredita que o programa, se viável, provavelmente levará cerca de 100 anos até que possa resolver o problema P vs. NP.
O programa é conduzido por diversos pesquisadores em matemática e ciência da computação teórica. Parte da razão para o interesse no programa é a existência de argumentos de que ele evita barreiras conhecidas, como a relativização e as provas naturais, para provar limites inferiores gerais..
Referências
Leitura adicional K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput. 31(2), 496–526, 2001.
K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput., 38(3), 1175–1206, 2008.
K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36 (2012), no. 1, 103–110.
K. D. Mulmuley. Geometric Complexity Theory V: Efficient algorithms for Noether normalization. J. Amer. Math. Soc. 30 (2017), no. 1, 225-309. arXiv:1209.5993 [cs.CC]
K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.
Ligações externas
GCT page, University of Chicago Description on the Simons Institute webpage GCT questions on cstheory Wikipedia-style explanation of Geometric Complexity Theory by Joshua Grochow What are the current breakthroughs of Geometric Complexity Theory? https://mathoverflow.net/questions/243011/why-should-algebraic-geometers-and-representation-theorists-care-about-geometric/
Categoria:Teoria da complexidade computacional Categoria:Teoria da computação