Y a-t-il un point de vue de complexité du théorème de Galois?

Le théorème de Galois dit effectivement que l'on ne peut pas exprimer les racines d'un polynôme de degré> = 5 en utilisant des fonctions rationnelles de coefficients et de radicaux - ne peut-on lire pour dire que, étant donné un polynôme, il n'y a pas d'algorithme déterministe pour trouver les racines?
Considérons maintenant une question de décision de la forme: "Étant donné un vrai polynôme enraciné et un nombre k est la troisième et la quatrième racine la plus élevée de au moins à un écart de k?" $p$ $p$

Un certificat de preuve pour cette question de décision ne sera que l'ensemble des racines de ce polynôme et c'est un certificat court et donc il semble que BUT n'est pas un théorème de Galois disant qu'il n'existe aucun algorithme déterministe pour trouver un certificat pour cette décision question? (et cette propriété si true exclut tout algorithme pour décider de la réponse à cette question) $NP$

Alors, dans quelle classe de complexité se situe cette question de décision?

Toutes les questions NP-complètes que j'ai vues ont toujours un algorithme de temps exponentiel trivial disponible pour les résoudre. Je ne sais pas si cela devrait être une propriété qui devrait toujours être vraie pour toutes les questions NP-complètes. Pour cette question de décision, cela ne semble pas être vrai.

complexity-theory np-complete np polynomials user6818
la source

Les racines sont un certificat mais il n'est pas évident pour moi qu'il s'agit d'un certificat court (c'est-à-dire qu'il existe une constante telle que, pour chaque polynôme, vous pouvez écrire ses racines en bits, où est le nombre de bits requis pour écrire le polynôme). Mais s'il existe un algorithme NP, il existe un algorithme trivial à temps exponentiel: il suffit d'énumérer tous les certificats potentiels et de voir si l'un d'eux fonctionne.

k

$k$

O (n^{k})

$O(n^k)$

n

$n$

David Richerby

Quelques commentaires: (1) Les racines de

ont des valeurs absolues au maximum . (2) Les séquences de Sturm peuvent être utilisées pour isoler les racines d'un polynôme. (3) On peut vérifier s'il y a deux racines à distance exactement , et si oui lesquelles, en calculant le GCD de et .

\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 Une de vos idées ci-dessus peut-elle être utilisée pour décider de la question de décision ci-dessus? Ce n'est pas évident si ceux-ci peuvent être utilisés pour trancher cette question - en temps polynomial?

user6818

"Le théorème de Galois dit effectivement que l'on ne peut pas exprimer les racines d'un polynôme de degré> = 5 en utilisant des fonctions rationnelles de coefficients et de radicaux - ne peut-on pas lire pour dire que, étant donné un polynôme, il n'y a pas d'algorithme déterministe pour trouver les racines? " Non, car les algorithmes polynomiaux temporels sont plus puissants que les fonctions rationnelles. Par exemple, ils peuvent diviser les cas, itérer, créer des tableaux et les boucler, etc.

sdcvvc

@ user6818 Le théorème concerne un modèle de calcul spécifique - les fonctions rationnelles des radicaux. Si vous modifiez le modèle, il ne s'applique plus. Par exemple, selon MathWorld mathworld.wolfram.com/QuinticEquation.html, il est possible de résoudre l'équation du 5e degré en utilisant les fonctions thêta de Jacobi. Si vous êtes bien avec un algorithme qui retourne la racine dans les 0,01 (ou tout donné

), le théorème de Galois ne sera plus disqualifier la méthode, car un nombre quelconque peut être approchée par un rationnel.

ϵ > 0

$\epsilon > 0$

sdcvvc

Réponses:

Connexion intéressante, mais la théorie de Galois affirme qu'il n'existe aucune méthode (cohérente) pour trouver les racines du quintique à l'aide de radicaux , au lieu de dire que le problème a une solution (par exemple, un chemin le plus long) qui peut nécessiter un temps super-polynomial. Je dirais donc que c'est plus lié à l'indécidabilité qu'à la complexité.

Plus précisément, dans la théorie de Galois, on construit progressivement des extensions de groupe des racines de l'équation, de manière progressive (en ajoutant une racine à la fois). Et tous ces groupes devraient être résolubles, en un sens il ne devrait y avoir aucune ambiguïté dans le processus de construction de ces extensions dans un autre ordre. Il y a une question connexe sur MO sur la complexité de la construction du groupe de Galois d'une équation .

Une autre référence ici "THEORIE GALOIS INFORMATIQUE: INVARIANTS ET CALCULS SUR ", CLAUS FIEKER JURGEN KLUNERS $\mathbb{Q}$

De plus, on peut systématiquement représenter les racines d'une euqation polynomiale utilisant des radicaux (lorsque l'équation est résoluble en utilisant des radicaux) basée sur la construction du ou des groupes de Galois de l'équation. Réf: "Représentation radicale des racines polynomiales", Hirokazu Anai Kazuhiro Yokoyama 2002

La complexité de calcul pour déterminer si un polynôme irréductible monique donné sur les entiers , est soluble par les radicaux est dans Ref "La solvabilité par les radicaux est en temps polynomial", S. Landau GL Miller 1984 $\mathbb{Z}$ $\mathbb{P}$

Une étude des récentes "Techniques de calcul des groupes de Galois", Alexander Hulpke

Bien sûr, si l'on recherche de bons algorithmes d'approximation et leur complexité (par exemple, la méthode de Newton ou le théorème de Sturm), c'est une question légèrement différente et la réponse déjà publiée fournit plus d'informations dans cette direction.

Nikos M.
la source

Merci! On dirait que je me suis accidentellement posé une question très excitante!

user6818

@ user6818, merci la réponse mise à jour avec plus d'informations et d'autres références

Nikos M.

Je suppose que vous envisagez des polynômes avec des coefficients entiers .

Vous avez pris le mauvais point de départ pour vos enquêtes; votre objectif est de trouver de bonnes estimations pour les vraies racines. La recherche d'une formule algébrique pour que vous puissiez l'évaluer avec une précision suffisante est quelque chose que vous pouvez faire, mais ce n'est pas vraiment la bonne chose à faire ici. (sauf, bien sûr, "la k-ème racine réelle d'un polynôme" est l'une de vos opérations algébriques)

Un bien meilleur point de départ est d'utiliser le théorème de Sturm pour isoler les racines du polynôme. Vous pouvez ensuite produire de meilleures estimations par recherche binaire, mais si c'est trop lent, vous pouvez utiliser la méthode de Newton pour produire rapidement des estimations de haute précision.

Mais il s'agit simplement de trouver des certificats. Il reste la question de savoir quels certificats peuvent exister.

Tout d'abord, je soulignerai que vous pouvez directement calculer si deux des racines sont exactement à unités l'une de l'autre, par exemple en calculant . Vous devrez également décider ce que vous voulez faire au sujet des racines répétées et les traiter de manière appropriée. Je suppose que vous vous occuperez spécialement de ces cas. $k$ $\gcd(p(x), p(x-k))$

Si nous savons que les deux racines ne sont pas exactement à unités l'une de l'autre, cela signifie que vous pouvez produire une estimation d'une précision suffisante pour prouver qu'elles sont soit supérieures ou inférieures à unités. Par exemple, il existe deux types de certificats: $k$ $k$

Le premier type (preuve négative) est

n'est pas une racine de $a$ $p$
n'a pas de racines dans $p$ $(a-k, a)$
a trois racines dans $p$ $(a, \infty)$

Le deuxième type (preuve positive) est

n'est pas une racine de $a$ $p$
a au moins deux racines dans $p$ $(a-k,a)$
a deux racines dans $p$ $(a, \infty)$

Un certificat peut être vérifié en utilisant le théorème de Sturm. Maintenant, votre question sur la taille d'un certificat se résume à trouver le nombre de bits de précision dont vous avez besoin pour représenter . $a$

En d'autres termes, quelles sont les limites des valeurs possibles de , où sont des racines de ? $a-b-k$ $a,b$ $f$

Je ne suis pas sûr d'une excellente approche, mais celle qui devrait vous donner quelque chose est d'observer que toutes ces valeurs sont les racines du polynôme:

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

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

Pourquoi? Rappelons que la résultante de deux polynômes moniques est le produit de toutes les différences de leurs racines, donc

g (X) = c^{{ré}^{2}} \prod_{une, b} (b - (une - X - k)) = \prod_{une, b} (X - (une - b - k))

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

où est le coefficient dominant et est le degré de . (j'ai peut-être écrit la formule de au lieu de ; je ne suis jamais sûr du signe) $c$ $d$ $f$ $-g(x)$ $g(x)$

La question est donc de trouver des estimations de la taille des coefficients , puis une fois que vous le savez, de trouver des estimations de la proximité d'une racine de à zéro. $g$ $g$

(ou, alternativement, trouver la plus grande ampleur qu'une racine du polynôme inverse de peut avoir; les racines du polynôme inverse sont les inverses des racines de ) $g$ $g$

la source

Y a-t-il des problèmes de représentation des données ici? NP concerne fondamentalement les machines de Turing et il n'est pas immédiatement évident de savoir comment cela se rapporte aux nombres réels ou au nombre de bits requis pour écrire des justifications d'une précision suffisante. (Je suis désolé de ne pas être très constructif: j'en sais assez pour savoir que cela pourrait être un problème mais pas assez pour savoir si c'est vraiment un problème ou, si c'est le cas, comment le résoudre.)

David Richerby

@DavidRicherby: Je suppose que les entrées ne sont essentiellement que les coefficients du polynôme écrit en binaire, et je m'attends à ce que le nombre de bits dont vous avez besoin pour représenter

en binaire soit limité par une fonction polynomiale du nombre de bits de contribution. Si nous utilisons deux paramètres, le nombre de bits d'entrée et le degré du polynôme, alors je suis presque certain que le nombre de bits dont vous avez besoin pour

sera polynôme dans le nombre de bits d'entrée, mais je suis moins sûr exactement comment cela dépendra du degré.

a

$a$

a

$a$

L'entrée sous forme de liste de coefficients est parfaitement logique. Mais vos hypothèses sur la précision nécessaire pour représenter les racines doivent certainement être vérifiées. Par exemple, la raison pour laquelle le dixième problème de Hilbert (résolution des équations diophantiennes) est indécidable est essentiellement que vous ne pouvez pas limiter la longueur de la solution en termes de longueur de l'entrée. Ce n'est pas directement applicable ici, car nous n'avons qu'une seule variable et nous ne recherchons pas de solutions entières, mais cela pose une assez grande question sur l'hypothèse de délimitation.

David Richerby

@David: La théorie des champs fermés réels est radicalement différente de la théorie des nombres; l'intuition sur l'un ne se traduit pas vraiment bien dans l'autre.

Et si deux racines sont distantes de

ou de

? Il peut être difficile de produire une estimation d'une précision suffisante.

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

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

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

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

Yuval Filmus

je vais prendre vos questions comme étant ouvertes. la preuve galoisienne maintenant connue sous le nom de thel Abel-Ruffini montre l'impossibilité des solutions polynomiales au quintique. (contrairement par exemple à l'équation quadratique). donc ce n'est pas vraiment un résultat sur la dureté d'un problème en soi mais plutôt sur l' impossibilité . en ce sens, il est plus analogue, par exemple, à une preuve d'indécidabilité du problème d'arrêt. la théorie de la complexité s'intéresse en général au «coût» des solutions informatiques. c'est le point de vue de deux éminents chercheurs CS dans la section introductive de cet article ( Computability and Complexity / Kleinberg & Papadimitriou), sec 1 The Quest for the Quintic Formula:

Vu de la distance de sécurité de quelques siècles, l'histoire est clairement une histoire de calcul, et elle contient de nombreux ingrédients clés qui surgissent dans les efforts ultérieurs pour modéliser le calcul: nous prenons un processus de calcul que nous comprenons intuitivement (résolution d'une équation , dans ce cas), formuler un modèle précis, et à partir du modèle dériver des conséquences très inattendues sur la puissance de calcul du processus. C'est précisément cette approche que nous souhaitons appliquer au calcul en général.

$\neq$ $\neq$

vzn
la source

Je ne suis pas sûr que le problème de l'arrêt soit une bonne analogie, car il ressemble davantage à "vous ne pouvez pas calculer la réponse" plutôt qu'à "il n'y a pas du tout de réponse".

Le théorème de Galois n'est-il pas un résultat d'impossibilité de calcul tout comme le problème de Halting?

user6818