Existe um ponto de vista de complexidade do teorema de Galois?

O teorema de Galois efetivamente diz que não se pode expressar as raízes de um polinômio de grau> = 5 usando funções racionais de coeficientes e radicais - não se pode ler que se está dizendo que, dado um polinômio, não há algoritmo determinístico para encontrar as raízes?
Agora considere uma questão de decisão da forma: "Dado um polinômio real com raiz e um número k é a terceira e a quarta raiz mais alta de pelo menos com uma diferença de k?" $p$ $p$

Um certificado de prova para esta questão de decisão será apenas o conjunto de raízes desse polinômio e esse é um certificado curto e, portanto, parece que MAS NÃO é o teorema de Galois dizendo que não existe nenhum algoritmo determinístico para encontrar um certificado para esta decisão questão? (e essa propriedade, se true, exclui qualquer algoritmo para decidir a resposta a esta pergunta) $NP$

Então, em que classe de complexidade está essa questão de decisão?

Todas as perguntas NP-completas que eu vi sempre têm um algoritmo de tempo exponencial trivial disponível para resolvê-las. Não sei se é esperado que essa seja uma propriedade que sempre deve ser verdadeira para todas as perguntas de NP-complete. Para esta questão de decisão, isso não parece ser verdade.

complexity-theory np-complete np polynomials user6818
fonte

As raízes são um certificado, mas não é óbvio para mim que elas são um certificado curto (ou seja, existe um constante, de modo que, para cada polinômio, você pode escrever suas raízes em bits, em que é o número de bits necessários para anotar o polinômio). Mas, se houver um algoritmo NP, existe um algoritmo trivial de tempo exponencial: apenas enumere todos os certificados em potencial e veja se algum deles funciona.

k

$k$

O (n^{k})

$O(n^k)$

n

$n$

David Richerby

Alguns comentários: (1) As raízes de têm valores absolutos no máximo . (2) Sequências de Sturm podem ser usadas para isolar as raízes de um polinômio. (3) Podemos verificar se existem duas raízes à distância exatamente , e se assim que, ao calcular o GCD de e .

\sum_{i = 0}^{n} a_{i} x_{i}

$\sum_{i=0}^n a_i x_i$

max (1, \sum_{i = 0}^{n - 1} | a_{i} | / | a_{n} |)

$\max(1,\sum_{i=0}^{n-1} |a_i|/|a_n|)$

k

$k$

p (x)

$p(x)$

p (x + k)

$p(x+k)$

Yuval Filmus

@YuvalFilmus Alguma das suas idéias acima pode ser usada para decidir a questão de decisão acima? Não é óbvio se eles podem ser usados para decidir esta questão - em tempo polinomial?

usar o seguinte comando

"O teorema de Galois efetivamente diz que não se pode expressar as raízes de um polinômio de grau> = 5 usando funções racionais de coeficientes e radicais - não se pode ler que se diz que, dado um polinômio, não há algoritmo determinístico para encontrar as raízes? " Não, pois os algoritmos de tempo polinomial são mais poderosos que as funções racionais. Por exemplo, eles podem dividir casos, iterar, criar matrizes e fazer um loop sobre eles, etc.

@ user6818 O teorema refere-se a um modelo de computação específico - funções racionais de radicais. Se você alterar o modelo, ele não será mais aplicado. Por exemplo, de acordo com o MathWorld mathworld.wolfram.com/QuinticEquation.html , é possível resolver a equação do quinto grau usando as funções teta de Jacobi. Se você está bem com um algoritmo que retorna a raiz dentro de 0,01 (ou qualquer ), o teorema de Galois não desqualifica mais o método, pois qualquer número pode ser aproximado por um racional.

ϵ > 0

$\epsilon > 0$

Sdcvvc

Respostas:

Conexão interessante, no entanto, a teoria de Galois afirma que não existe um método (consistente) para encontrar raízes do quintic usando radicais , em vez de dizer que o problema tem uma solução (por exemplo, um caminho mais longo) que pode exigir tempo super-polinomial. Então, eu diria que está mais relacionado à indecidibilidade do que à complexidade.

Especificamente, na teoria de Galois, constrói-se progressivamente extensões de grupo das raízes da equação, passo a passo (adicionando uma raiz de cada vez). E todos esses grupos devem ser solucionáveis, em certo sentido, não deve haver ambiguidade no processo de construção dessas extensões em outra ordem. Existe uma pergunta relacionada a MO sobre a complexidade de construir o grupo Galois de uma equação .

Outra referência aqui "TEORIA COMPUTACIONAL DE GALOIS: INVARIANTES E COMPUTAÇÕES SOBRE ", CLAUS FIEKER JURGEN KLUNERS $\mathbb{Q}$

Além disso, pode-se representar sistematicamente raízes de uma euqação polinomial usando radicais (quando a equação é solucionável usando radicais) com base na construção do (s) grupo (s) de Galois da equação. Ref: "Representação radical de raízes polinomiais", Hirokazu Anai Kazuhiro Yokoyama 2002

A complexidade computacional de determinar se um dado polinômio monômico irredutível sobre os números inteiros é solúvel por radicais está em Ref "A solvabilidade dos radicais está no tempo polinomial", S. Landau GL Miller 1984 $\mathbb{Z}$ $\mathbb{P}$

Uma pesquisa recente "Técnicas para a Computação de Grupos Galois", Alexander Hulpke

Obviamente, se alguém está procurando bons algoritmos de aproximação e sua complexidade (por exemplo, o método de Newton ou o Teorema de Sturm), essa é uma pergunta um pouco diferente e a resposta já postada fornece mais informações nessa direção.

Nikos M.
fonte

Obrigado! Parece que acidentalmente me fiz uma pergunta muito emocionante!

usar o seguinte comando

@ user6818, graças resposta atualizado com mais informações e outras referências

Nikos M.

Suponho que você esteja considerando polinômios com coeficientes inteiros .

Você tomou o ponto de partida errado para suas investigações; seu objetivo é encontrar boas estimativas para as raízes reais. Procurar uma fórmula algébrica para que você possa avaliá-la com precisão suficiente é algo que você pode fazer, mas não é realmente a coisa certa a fazer aqui. (a menos que, é claro, "a k-a maior raiz real de um polinômio" seja uma de suas operações algébricas)

Um ponto de partida muito melhor é usar o teorema de Sturm para isolar as raízes do polinômio. Em seguida, é possível produzir melhores estimativas por pesquisa binária, mas se isso for muito lento, você poderá usar o método de Newton para produzir rapidamente estimativas de alta precisão.

Mas isso é apenas sobre encontrar certificados. Ainda há a questão de quais certificados podem existir.

Primeiramente, vou apontar que você pode calcular diretamente se duas das raízes estão exatamente unidades separadas, por exemplo, computando . Você também terá que decidir o que deseja fazer sobre as raízes repetidas e lidar adequadamente. Presumo que você lide com esse caso especialmente. $k$ $\gcd(p(x), p(x-k))$

Se sabemos que as duas raízes não estão exatamente unidades separadas, isso significa que você pode produzir uma estimativa de precisão suficiente para provar que elas são maiores ou menores que unidades separadas. por exemplo, existem dois tipos de certificados: $k$ $k$

O primeiro tipo (prova negativa) é

$a$ não é uma raiz de $p$
$p$ não tem raízes em $(a-k, a)$
$p$ tem três raízes em $(a, \infty)$

O segundo tipo (prova no positivo) é

não é uma raiz de $a$ $p$
tem pelo menos duas raízes em $p$ $(a-k,a)$
tem duas raízes em $p$ $(a, \infty)$

Um certificado pode ser verificado usando o teorema de Sturm. Agora, sua pergunta sobre o tamanho de um certificado se resume a encontrar quantos bits de precisão você precisa para representar . $a$

Em outras palavras, quais são os limites dos possíveis valores de , onde são raízes de ? $a-b-k$ $a,b$ $f$

Não tenho certeza de uma ótima abordagem, mas uma que deve lhe dar alguma coisa é observar que todos esses valores são raízes do polinômio:

g (x) = {Res}_{y} (f (y), f (x + y + k))

$g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k))$

Por quê? Lembre-se de que o resultado de dois polinômios monônicos é o produto de todas as diferenças de suas raízes;

g (x) = c^{d^{2}} \prod_{a, b} (b - (a - x - k)) = \prod_{a, b} (x - (a - b - k))

$g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k)) = \prod_{a,b} (x - (a-b-k))$

$c$ $d$ $f$ $-g(x)$ $g(x)$

$g$ $g$

fonte

Há algum problema sobre representação de dados aqui? O NP é fundamentalmente sobre as máquinas de Turing e não é imediatamente óbvio como isso se relaciona com números reais ou o número de bits necessários para anotar racionais de precisão suficiente. (Sinto muito por não ser muito construtivo: sei o suficiente para saber que isso pode ser um problema, mas não o suficiente para saber se é realmente um problema ou, se for, como resolvê-lo.)

David Richerby,

a

$a$

a

$a$

A entrada como uma lista de coeficientes faz todo sentido. Mas suas suposições sobre a precisão necessária para representar as raízes definitivamente precisam ser verificadas. Por exemplo, a razão pela qual o décimo problema de Hilbert (solução de equações diofantinas) é indecidível é essencialmente que você não pode limitar o comprimento da solução em termos do comprimento da entrada. Isso não é diretamente aplicável aqui, já que temos apenas uma variável e não estamos procurando soluções inteiras, mas faz uma grande pergunta sobre a suposição de limite.

David Richerby

@ David: A teoria dos campos fechados reais é dramaticamente diferente da teoria dos números; a intuição sobre um não se traduz realmente bem no outro.

k + 2^{- 2^{2^{n}}}

$k+2^{-2^{2^n}}$

k - 2^{- 2^{2^{n}}}

$k-2^{-2^{2^n}}$

vou responder às suas perguntas como geralmente abertas. a prova de galois, agora conhecida como Abel-Ruffini thm, mostra a impossibilidade de soluções polinomiais para o quintic. (em contraste com, por exemplo, a equação quadrática). portanto, não é realmente um resultado da dureza de um problema em si, mas da impossibilidade . nesse sentido, é mais análogo, por exemplo, uma prova de indecidibilidade do problema da parada. A teoria da complexidade está geralmente preocupada com o "custo" das soluções de computação. esse é o ponto de vista de dois pesquisadores de CS líderes na seção introdutória deste artigo a seguir ( Computability and Complexity / Kleinberg & Papadimitriou), seção 1 The Quest for the Quintic Formula:

Visto a uma distância segura de alguns séculos, a história é claramente sobre computação e contém muitos dos principais ingredientes que surgem em esforços posteriores para modelar a computação: Adotamos um processo computacional que compreendemos intuitivamente (resolvendo uma equação , nesse caso), formule um modelo preciso e, a partir do modelo, derivam algumas conseqüências altamente inesperadas sobre o poder computacional do processo. É precisamente essa abordagem que desejamos aplicar à computação em geral.

$\neq$ $\neq$

vzn
fonte

Não tenho certeza de que o problema da parada seja uma boa analogia, pois é mais parecido com "você não pode calcular a resposta" em vez de "não há resposta nenhuma".

O teorema de Galois não é um resultado de impossibilidade computacional como o problema de Halting?

usar o seguinte comando