Programa GCT de Mulmuley

38

Às vezes, afirma-se que a Teoria da Complexidade Geométrica de Ketan Mulmuley é o único programa plausível para resolver as questões abertas da teoria da complexidade, como a questão P vs. NP. Houve vários comentários positivos de famosos teóricos da complexidade sobre o programa. Segundo Mulmuley, levará muito tempo para alcançar os resultados desejados. Não é fácil entrar na área para os teóricos da complexidade geral e precisa de esforços consideráveis ​​para lidar com a geometria algébrica e a teoria da representação.

  1. Por que o GCT é considerado capaz de resolver P vs. NP? Qual é o valor da reivindicação, caso se espere mais de 100 anos para chegar lá? Quais são suas vantagens para outras abordagens atuais e aquelas que podem aumentar nos próximos 100 anos?

  2. Qual é o estado atual do programa?

  3. Qual é o próximo objetivo do programa?

  4. Houve alguma crítica fundamental ao programa?

Eu preferiria respostas que sejam compreensíveis por um teórico da complexidade geral com o mínimo de experiência em geometria algébrica e teoria da representação assumida.

Anônimo
fonte
12
Você viu o tutorial de Mulmuley no FOCS (disponível em techtalks.tv/talks/1301 ) e leu a exposição de Ken Regan: theoryie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Mulmuley definitivamente deu sua intuição por que ele acha que seu programa é viável (e acho que ele argumenta que é até certo ponto necessário), e também por que é difícil.
Sasho Nikolov
5
Postagens de blog relacionadas: 1 , 2 . Scott também escreve: "O programa GCT de Mulmuley é a única abordagem para P vs. NP que eu já vi que tem sérias aspirações de" conhecer "muitas técnicas não triviais para resolver problemas em P (pelo menos, programação linear e de correspondência) Para mim, esse é provavelmente o argumento mais forte a favor do GCT. "
precisa
7
Eu acho que o GCT está visando VP vs. VNP e não P vs NP.
Iddo Tzameret
6
@ Iddo: Na verdade, pode ser direcionado para muitas coisas (mais do que é atualmente direcionado). Para "perm v det over ", ele visa ¯ V P w s vs V N P (consulte arxiv.org/abs/0907.2850 ). No entanto, em campos finitos e para outras funções que não sejam perm e det, ele pode ser direcionado diretamente para P vs NP.CVPWs¯VNP
Joshua Grochow
4
@ Mohammad: Só porque uma solução seria inesperada e exigiria idéias totalmente novas não significa que não é assim que a solução será. De fato, muitos já acreditam que resolver P vs NP por qualquer método exigirá idéias inteiramente novas ...
Joshua Grochow

Respostas:

23

Como apontado por muitos outros, já foi dito muito sobre muitas dessas perguntas por Mulmuley, Regan e outros. Vou oferecer aqui apenas um breve resumo do que acho que são alguns pontos-chave que ainda não foram mencionados nos comentários.

  1. Por que o TCG é considerado plausivelmente capaz de mostrar muitas respostas já foram dadas em outros lugares e nos comentários acima, embora eu ache que ninguém ainda tenha mencionado que parece evitar as barreiras conhecidas (relativização, algebrização, provas naturais ) Quanto ao seu valor - acho que, mesmo que demore 100 anos, aprenderemos algo novo sobre complexidade ao longo do caminho, estudando-a desse ângulo.PNP

    • Algum progresso está sendo feito no entendimento das variedades algébricas, das representações e das questões algorítmicas que surgem no TCG. Os principais pesquisadores que conheço que fizeram trabalhos sobre isso são (em nenhuma ordem específica): P. Burgisser, C. Ikenmeyer, M. Christandl, JM Landsberg, KV Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar e, é claro, K. Mulmuley e M. Sohoni.

    • Mais concretamente, Burgisser e Ikenmeyer acabaram de apresentar (STOC 2011) alguns limites inferiores modestos na multiplicação de matrizes usando a abordagem GCT ( , em comparação com o atualmente mais conhecidon2+232n2+O(n)

    • N. Kayal tem alguns artigos sobre a questão algorítmica de teste quando um polinômio está na órbita de outro ou é uma projeção de outro. Ele mostra que, em geral, esses problemas são difíceis de NP, mas que, para funções especiais como polinômios simétricos permanentes, determinantes e elementares, esses problemas são decidíveis em P. Este é um passo em direção a algumas das conjecturas de Mulmuley (que certos problemas mais difíceis - decidir órbita encerramento - estão em P para funções especiais, como determinante).

  2. Eu não tenho muito mais específico a dizer sobre isso do que a resposta para 2.

  3. Até onde eu sei, não houve críticas fundamentais , no sentido de que não vi nenhuma crítica que realmente desacredite o programa de forma alguma. Certamente houve discussões sobre o porquê de tais técnicas serem necessárias, o valor do programa, considerando os longos horizontes esperados, etc., mas eu os caracterizaria mais como uma discussão saudável do que uma crítica fundamental.

Joshua Grochow
fonte
1
@ user124864: Em princípio, sim. O TCG é apenas uma abordagem para mostrar limites inferiores, quaisquer que sejam esses limites inferiores. Parece que deveria funcionar melhor para funções caracterizadas por suas simetrias, mas a última propriedade não depende do valor numérico do limite inferior que você deseja mostrar (por exemplo, quasipoly vs exp).
Joshua Grochow