Como a abordagem geométrica de Mulmuley-Sohoni para produzir limites inferiores evita produzir provas naturais (no sentido Razborov-Rudich)?

22

A redação exata do título deve-se a Anand Kulkarni (que propôs a criação deste site). Esta pergunta foi feita como exemplo, mas estou insanamente curiosa. Eu sei muito pouco sobre geometria algébrica e, de fato, também só tenho uma compreensão superficial dos obstáculos em jogo na questão P / poli versus NP (não relativização, não álgebra, provavelmente não será uma prova natural) .

O que faz a geometria algébrica parecer que pode contornar esse tipo de obstáculo? É apenas intuição de especialista em campo ou temos realmente um bom motivo para acreditar que a abordagem é fundamentalmente mais poderosa do que as abordagens anteriores? Que resultados mais fracos essa abordagem conseguiu alcançar?

Ross Snider
fonte

Respostas:

19

[Responderei à pergunta conforme declarado no título, deixando a litania de outras perguntas sobre o GCT para outros tópicos.] e outros polinômios relacionados para P / poli e NP) são caracterizados por suas simetrias. Essa necessidade não é um resultado formal, mas uma intuição expressa por vários especialistas. (Basicamente, na ausência de caracterização por simetrias, é muito mais difícil entender a geometria algébrica e a teoria da representação que surge.)

Isso deve ignorar Razborov-Rudich porque muito poucas funções são caracterizadas por suas simetrias (ignorando a condição de grandeza na definição de provas naturais). Mais uma vez, não vi uma prova disso, mas é uma intuição que ouvi expressa por vários especialistas.

Agora, além dos números complexos, não está claro para mim que exista um análogo de Razborov-Rudich. Embora a maior parte do GCT atualmente se concentre em números complexos, existem análogos na característica finita (prometida no próximo artigo GCT VIII). Na característica finita, pode-se realmente provar uma afirmação da forma "Muito poucas funções são caracterizadas por suas simetrias".


[Em resposta ao comentário de Ross Snider, aqui está uma explicação da caracterização por simetrias.]

Primeiro, uma explicação por exemplo. Para o exemplo, defina uma função auxiliar . Se A é uma matriz de permutação, então q ( A ) = 1 e se A é diagonal, então q ( A ) = d e t ( A ) (produto das entradas diagonais). Agora, suponha que p ( X ) é um grau homogênea n polinomial em n 2 variáveis (que nós pensamos como os entires de um n × n matriz XqAq(A)=1Aq(A)=det(A)p(X)nn2n×nX) Se tiver as seguintes simetrias:p

  • (transposição)p(X)=p(Xt)
  • para todos os pares de matrizes ( A , B ), de modo que A e B sejam matrizes de permutação ou matrizes diagonais e q ( A ) q ( B ) = 1p(AXB)=p(X)(A,B)ABq(A)q(B)=1

em seguida, é um múltiplo constante da p e r m ( X ) para todas as matrizes X . Por isso, dizemos que a permanente é caracterizada por suas simetrias.p(X)perm(X)X

De modo mais geral, se tivermos um (homogénea) polinomial de m variáveis, em seguida, L L m (o grupo de todos invertível m × m matrizes) actua em f por ( A f ) ( x 1 , . . . , x m ) = f ( A - 1 ( x 1 ) ,f(x1,...,xm)mGLmm×mf para um L L m (em que estão a tomar as variáveis x 1 , . . . , X m como uma base para a m de espaço vectorial -dimensional em que G G m actua naturalmente). O estabilizador de f em G L m é o subgrupo Stab ( f ) = { A G(Af)(x1,...,xm)=f(A1(x1),...,A1(xm))AGLmx1,...,xmmGLmfGLm . Dizemos que f é caracterizado por suas simetrias se o seguinte for válido: para qualquer polinômio homogêneo f em m variáveis ​​do mesmo grau que f , se A f = f para todos os A Stab ( f ) , então f é um múltiplo constante de f .Stab(f)={AGLm:Af=f}ffmfAf=fAStab(f)ff

Joshua Grochow
fonte
Parece uma ótima resposta, mas receio não entender um pouco as simetrias de funções (o que significa que estou perdendo os detalhes cruciais da resposta). Você poderia descompactar qual é a simetria de uma função, por que seria importante para poucas funções caracterizadas por ela (aka - por que isso permitiria ignorar a condição de grandeza de Razborov)? Também para ficar claro, sua resposta é que existe uma mistura. Há razões pelas quais a abordagem parece promissora, mas, em última análise, a evidência dessas razões se deve em grande parte à intuição de especialistas.
Ross Snider
4
Eu adicionei uma explicação de caracterização por simetrias para você. Mesmo que poucas funções sejam caracterizadas por suas simetrias, ainda estamos contando com a intuição de especialistas de que a caracterização por simetrias será crucial para provar as conjecturas que surgem no TCG. Se esse for realmente o caso, as técnicas de prova usadas nessas conjecturas funcionariam apenas para uma pequena fração de funções, ignorando assim a condição de grandeza. (Ou era isso o que você estava perguntando?)
Joshua Grochow
Ooooh. Epifania gravada aqui. Muito obrigado. Como posso não aceitar esta resposta?
Ross Snider
15

P/polyNPP/polySATP/polySATNPNP

Em outras palavras, Razborov – Rudich geralmente não apresenta muitos obstáculos nos estágios iniciais do planejamento de uma linha de ataque nos limites inferiores do circuito, desde que você deixe algum espaço em seu plano para eventualmente empregar "propriedades especiais" de suas funções booleanas candidatas. Somente quando você arregaça as mangas e tenta preencher os detalhes do argumento é que a barreira da naturalização começará a levantar a cabeça a sério. Dado que o GCT ainda está em um estágio inicial de desenvolvimento, ainda não devemos esperar muito se preocupar com a naturalização (embora, é claro, valha a pena verificar se o programa GCT não está condenado por razões triviais).

Você também pode conferir a exposição de Ken Regan sobre o TCG, que inclui algumas observações sobre a barreira da naturalização.

Timothy Chow
fonte