Incertezas no programa GCT

Em https://en.wikipedia.org/wiki/Geometric_complexity_theory , é mencionado que ".. Ketan Mulmuley acredita que o programa, se viável, provavelmente levará cerca de 100 anos para resolver o problema P vs. NP".

Parece indicar que o único programa atualmente viável poderia enfrentar sérios obstáculos.

Quais são alguns dos obstáculos em que o programa pode falhar?

Depende do que você conta como "o programa GCT".

1. Considere a sugestão específica ( GCT I , GCT II ) de usar o desaparecimento / não desaparecimento de certas multiplicidades nos fechamentos de órbita do determinante e permanente para resolver a forte conjectura permanente versus determinante (ou seja, que o permanente não está no fechamento da órbita de qualquer determinante polinomialmente maior). Nesse caso, é possível que, mesmo que a conjectura seja verdadeira, isso não se reflita no desaparecimento / não desaparecimento de multiplicidades de irreps suportadas nesses fechamentos de órbita. É até possível que a conjectura não se reflita na desigualdade apropriada de multiplicidades. Devo observar que existem várias formas de evidência de que isso não deveria acontecer, mas ainda não foi formalmente descartado.

Observe, no entanto, que se em vez de multiplicidades você apenas deseja um módulo de separação , a forte conjectura perm v det é verdadeira se, e somente se , existir um módulo de separação.

2. Se o seu objetivo é a conjectura original permanente versus determinante, há um passo anterior no TCG, a saber (como apontado por chazisop), movendo-se para a forte conjetura perm v det considerando os fechamentos da órbita . É concebível que a conjectura original permanente versus determinante seja verdadeira, mas a versão forte seja falsa. No entanto, isso parece altamente improvável para mim. Além disso, se essa for a situação, nenhum dos nossos métodos atuais pode nem chegar perto de resolver a conjectura perm v det, pois todos atualmente trabalham para a versão "forte" / "aproximativa" / "fronteira -" / versão fechada por Zariski de qualquer declaração de complexidade algébrica que eles estejam provando.

3. Se seu objetivo não for permitido, mas Booleano , existem outras etapas reivindicadas no GCT que ainda não foram publicadas. É possível que uma dessas etapas não publicadas também falhe, mas obviamente é difícil comentar sobre os detalhes da matemática que não se viu ...$\mathsf{NP} \not\subseteq \mathsf{P/poly}$

4. [Falhas potenciais dos limites inferiores em geral, não específicas para o TCG.] Atualmente, o TCG é voltado para limites inferiores não uniformes; isto é, mesmo na abordagem GCT para os limites inferiores booleanos, ele visa mostrar . Mas é claro, é consistente com os teoremas atuais que ainda . Obviamente, também é tecnicamente possível que e a conjectura perm v det sejam falsas!$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP} \subseteq \mathsf{P/poly}$$\mathsf{P} = \mathsf{NP}$

No entanto, deixe-me salientar que o programa GCT como existe atualmente ainda me parece a primeira coisa a tentar . Se, de fato, qualquer um dos itens (1) - (3) acima não funcionar, significa que a conjectura perm v det (e, portanto, versus ) é quase inimaginavelmente mais difícil do que pensamos atualmente. (Pode ser interessante notar que essa afirmação vem de alguém que já pensa que a analogia a seguir pode estar aproximadamente correta, se não inadequada: corresponde ao nosso estado atual de conhecimento como o A classificação de grupos simples finitos refere- se ao pequeno teorema de Fermat ). E mesmo se for esse o caso,$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$compreender a maneira exata pela qual a falha ocorre provavelmente será importante para avançar ainda mais .

Acredito que a afirmação "100 anos" refere que a teoria é geral, mas requer compreensão profunda e novos resultados na teoria das representações e na geometria algébrica para progredir, algo que pode demorar para progredir (eu quero fazer uma comparação com a teoria dos números, mas Não sei ao certo como é adequado).

Além disso, há uma perda de precisão ao traduzir para o mundo algebro-geométrico: em vez de provar um limite inferior às propriedades de uma classe de complexidade (ou seja, polinômios que desaparecem quando objetos dessa classe são dados como entrada), você está provando isso contra seu fechamento de Zariski (dos polinômios acima mencionados). É concebível que, para separar os dois, seja necessário examinar o limite desse fechamento (os polinômios que ocorrem apenas no fechamento, mas no conjunto original). Acredita-se que na variante determinante versus permanente do programa GCT, esse é provavelmente o caso .

Finalmente, por experiência pessoal, o conjunto de habilidades necessárias para entender o TCG em profundidade é bem diferente do que normalmente é o foco dos cursos de graduação ou mesmo mestrado em CS, essencialmente, atender aos pré-requisitos é um acompanhamento natural da escolha de estudar o TCG.