Un probléme à 1 million de dollards.

[invite3ed13054]

Bonjour,

Voici un probléme mathématiques faciles à énoncer (équivalent à NP?=P) :
Etant donné un corps fini de type Zp (avec p un grand entier premier) et un polynôme avec un grand degré qui consiste en élévation à de grande puissance de petites sommes de petits monomes par exemple (X^2+X+2)^(2^1000) (de degré plus petit que 2) et a de petite multiplication (moins de 5 termes) et des additions (moins de 10000 termes).
Existe-t-il un algo raisonnable (polynomiale en temps) qui soit capable de dire si un tel polynôme a des solutions sur Zp ou non ?

Cordialement.
-----

[invite51d17075]

bjr,
c'est juste que je n'y comprend rien !

[invite3ed13054]

Bjr,
Pour le dire autrement on cherche un algo de complexité polynomiale qui résout le problème de savoir si oui ou non un polynôme à une indétermiée a des racines dans un corps Zp.

[Médiat]

Bonjour,

Dans Z_p il n'y a que p éléments ... il suffit de les essayer tous, non ?

[A voir en vidéo sur Futura]

[invite3ed13054]

Bonjour,

Dans Z_p il n'y a que p éléments ... il suffit de les essayer tous, non ?

Bonjour,

On pourrait mais alors la complexité serait exponentielle (p~2^n, n~1000).

[Médiat]

Mais cela reste proportionnel à p.

Sinon, tout problème polynomial en p deviendrait exponentiel en disant que p = 2^n

[invite3ed13054]

En l'occurence, ici, la complexité pour rester raisonnable doit être O(P(n)). (P un polynôme)

[gg0]

O(n)=O(P(n))
avec P le polynôme défini par P(x)=x.

[invite3ed13054]

O(n)={f:n->f(n)/ il existe M constante tel que f(n)<M*n}.
Trouver un algo d'une complexité linéaire serait géniale, mais trés difficile en une seule tentative.
P(n) est différent du polynôme dont je parle dans le problème.

[Seirios]

Bonjour,

Dans le même ordre d'idée, on trouve An elementary problem equivalent to the Riemann hypothesis.

[invite3ed13054]

Bonjour,

Oubliez alors l'argent et faîtes le pour la Science.

Cordialement.

[inviteea028771]

Mais cela reste proportionnel à p.

Sinon, tout problème polynomial en p deviendrait exponentiel en disant que p = 2^n

A mon avis, on doit vouloir un truc polynomial par rapport à la taille de p (et non pas à sa valeur)

Un peu comme pour la décomposition en facteurs premiers, ou même un algorithme naïf est dans le pire des cas linéaire par rapport à la valeur du nombre (mais pas par rapport à la taille de l'entrée)

[invite7a96054d]

Bonjour,

Voici un probléme mathématiques faciles à énoncer (équivalent à NP?=P) :
Etant donné un corps fini de type Zp (avec p un grand entier premier) et un polynôme avec un grand degré qui consiste en élévation à de grande puissance de petites sommes de petits monomes par exemple (X^2+X+2)^(2^1000) (de degré plus petit que 2) et a de petite multiplication (moins de 5 termes) et des additions (moins de 10000 termes).
Existe-t-il un algo raisonnable (polynomiale en temps) qui soit capable de dire si un tel polynôme a des solutions sur Zp ou non ?

Cordialement.

Bonjour,

Tu proposes un problème de décision que je peux réécrire ainsi (tu m'arrêtes si j'ai mal compris ton énoncé) :
Dans Z_p,
En entrée : un polynome P de degré n
En sortie : oui s'il existe un élément a du corps tel P(a)=0, non sinon

Évaluer un polynome en un point a est en Θ(n) en utilisant l'algorithme de Horner. Comme le fait à juste titre remarquer Mediat, pour obtenir la réponse il faut au pire évaluer le polynome en p points. Donc un algo simple comme :

test( P : polynome )
debut
  pour chaque a de Zp faire
    si evaluation(P,a)=0 alors
      afficher OUI
      fin du programme
    fin si
  fin pour
  afficher NON
fin

où evaluation est une fonction qui évalue le polynome P au point a en utilisant l'algorithme de Horner. Quel que soit le polynome, dans le pire des cas, on passe p fois dans la boucle ;
Voilà donc un algo en Θ(n) (n étant le degré du polynome, ce qui est mesuré est le nombre d'additions et de multiplications).
J'ai peut-être mal compris ou je me suis planté quelque part?

[invite3ed13054]

Bonjour,

Tu proposes un problème de décision que je peux réécrire ainsi (tu m'arrêtes si j'ai mal compris ton énoncé) :
Dans Z_p,
En entrée : un polynome P de degré n
En sortie : oui s'il existe un élément a du corps tel P(a)=0, non sinon ...

Bonjour,

En fait le polynôme serait de degré d'ordre 2^(n+2) et p d'ordre 2^n.

Cordialement.

[inviteaf1870ed]

En tous cas on peut affirmer que Dollar ne prend qu'un seul D, même quand il y en a un million

[invite7a96054d]

OK,
le polynome est de degré N=2^(n+2), p devient dépendant de N : P=N/4. L'algorithme proposé a une complexité en Θ(PN) (on boucle au pire P fois sur une fonction qui coûte en N), la complexité est donc en Θ(N²).
La complexité augmente car le nombre d'éléments du corps devient dépendant du degré du polynome. Il n'y a pas explosion exponentielle, ce n'est que le degré du polynome qui est très grand.

[invite3ed13054]

Tu sembles sous-entendre que la complexité sera nécessairement au moins aussi importante que le degré du polynôme.
Si tu peux en donner un exemple, alors tu mérites largement les 1 millions.

[invite3ed13054]

OK,
le polynome est de degré N=2^(n+2), p devient dépendant de N : P=N/4. L'algorithme proposé a une complexité en Θ(PN) (on boucle au pire P fois sur une fonction qui coûte en N), la complexité est donc en Θ(N²).
La complexité augmente car le nombre d'éléments du corps devient dépendant du degré du polynome. Il n'y a pas explosion exponentielle, ce n'est que le degré du polynome qui est très grand.

Le coût de calcul P(a) pour a fixé dans le corps est quasi-constant et de complexité O(Q(n)) (Q un polynôme et log_2(a)~n).

[invite7a96054d]

Le coût de calcul P(a) pour a fixé dans le corps est quasi-constant et de complexité O(Q(n)) (Q un polynôme et log_2(a)~n).

Heu ... je ne comprends pas ce que tu cherches à exprimer ...

Si P est un polynome de degré N dont les coef sont constants = ne dépendent pas de N, alors en utilisant l'algorithme de Horner (ou pas d'ailleur, cela est vrai aussi pour l'évaluation directe) alors l'évaluation de P en a est en Θ(N) (plus restrictif que O(N)) additions et multiplications. L'addition et la multiplication sont des opérations en temps constant.
Est-on ok sur ce point ?

[invite3ed13054]

Heu ... je ne comprends pas ce que tu cherches à exprimer ...

Si P est un polynome de degré N dont les coef sont constants = ne dépendent pas de N, alors en utilisant l'algorithme de Horner (ou pas d'ailleur, cela est vrai aussi pour l'évaluation directe) alors l'évaluation de P en a est en Θ(N) (plus restrictif que O(N)) additions et multiplications. L'addition et la multiplication sont des opérations en temps constant.
Est-on ok sur ce point ?

Bonjour,
Non, en effet si on prend par exemple le polynôme (X+1)^(2^n) alors on l'évalue en faisant n opération carré et pas de l'ordre de 2^n opération élémentaire.
Cordialement.

[invite7a96054d]

Bonjour,
Non, en effet si on prend par exemple le polynôme (X+1)^(2^n) alors on l'évalue en faisant n opération carré et pas de l'ordre de 2^n opération élémentaire.
Cordialement.

Au temps pour moi, je n'étais pas assez précis, je parlais évidemment pas d'un cas particulier mais du temps dans le pire des cas. Si tu restreins le problème à des cas très précis tu peux effectivement trouver des algorithmes avec des complexités moins élevées mais cela te prive du million de dollar car le problème est différents.

Donc ton problème de décision devient:

pour un N donné on de place dans Z_N
question : existe-t-il un élément x de Z_N tel que pour le monome P(X)=(aX+b)^N on a P(x)=0 ?

[invite3ed13054]

Etant donné un corps fini de type Zp (avec p un grand entier premier) et un polynôme avec un grand degré qui consiste en élévation à de grande puissance de petites sommes de petits monomes par exemple (X^2+X+2)^(2^1000) (de degré plus petit que 2) et a de petite multiplication (moins de 5 termes) et des additions (moins de 10000 termes).
Existe-t-il un algo raisonnable (polynomiale en temps) qui soit capable de dire si un tel polynôme a des solutions sur Zp ou non ?

Maintenant si tu as un exemple ou la complexité est néssairement de l'ordre de p (p un grand entier premier), je serais trés heureux de le connaître.

[invite7a96054d]

Tu répètes ta première proposition dans laquelle p est indépendant de N le degré du polynome ...
Je t'ai déjà donné la réponse, tu appliques l'algorithme de Horner p fois : une fois pour chaque élément a de Zp. Cela te donne un algorithme en grand théta de N (l'ordre du polynome) : c'est un polynome dont la complexité est polynomiale (coût mesuré le nombre d'additions et multiplications) par rapport à l'ordre du polynome. Le fait de poser N=2ⁿ ne change rien ...

[invite3ed13054]

Je comprends, et si tu veux on cherche un algo de complexité O(Q(ln(p))) ( avec Q un polynome ).
P étant tel que l'on puisse évaluer P en n'importe quelle élément du corps en un temps raisonnable.

[invite7a96054d]

Bon je ne suis pas un spécialiste en la matière, mais tu vas avoir du mal car pour évaluer un polynome quelconque de degré n il va falloir au minimum connaître les coef de ce polynome et il y en a au pire n+1 -> un algo a une complexité minimale en O(n) en terme d'additions/multiplications.

Si tu passes à un autre problème, à savoir te restreindre à des polynome du genre (aX²+bX+c)^n, alors effectivement l'évaluation sera moins coûteuse mais ce n'est plus le même problème ...

Définis clairement le problème sans essayer d'utiliser 2^n.

[invite3ed13054]

Entrée : p un nombre premier, P un polynôme sur Zp tel qu'on ait un algo O(Q(ln(p)) pour évaluer P(a) avec a dans Zp.
Sortie : oui, si P a une racine sur Zp ou non sinon.

On cherche un algo de complexité O(Q(ln(p))) résolvant se probléme ou un exemple de P et p tel que la complexité ne serait pas de cette ordre.

[invite7a96054d]

OK, donc le degré de polynome est indépendant de p et le polynome est quelconque ... c'est bien ça ?

Si c'est ça la formulation pourrait être :

Entrée : p un nombre premier, P un polynôme sur Zp de degré n
Sortie : oui, si P a une racine sur Zp ou non sinon.

[invite3ed13054]

Entrée : p un nombre premier, P un polynôme sur Zp dont on peut évaluer raisonnablement P(a) pour un a quelconque dans Zp.
Sortie : oui, si P a une racine sur Zp ou non sinon.

Et on cherche un algo de complexité O(Q(ln(p))) qui résout ce probléme.

[invite7a96054d]

Il faut être plus précis sur le « P un polynôme sur Zp dont on peut évaluer raisonnablement P(a) pour un a quelconque dans Zp.» ...
Raisonnablement ça signifie quoi ? qu'il existe un algorithme qui évalue P en O(n) multiplications/additions avec n le degré du polynome ?

[invite3ed13054]

Raisonnablement = moins de 10^6 multiplications/additions.