Un probléme à 1 million de dollards.

[invite7a96054d]

cela ne signifie pas grand chose, tu penses à O(1) ?
Tu penses à l'ensemble des polynomes P dont l'évaluation en un point par l'application d'un certain algorithme prendra moins 10^6 additions/multiplications ?
-----

[invite3ed13054]

Je pense à O(ln(p)^3) par exemple.
Je répéte raisonnable renvoie à la complexité de l'algo que je cherche en l'occurence ici O(Q(ln(p))).
En effet quand on cherche un algo on veut qu'il ait une complexité raisonnable (non ?).

En espérant être claire.

[invite7a96054d]

Tu parles de polynomes dont on peut évaluer la valeur en temps raisonnable ... nous n'en sommes que là. Si les polynomes sont quelconques tu ne pourras trouver mieux que O(n) avec n le degré du polynome. Si tu restreins les polynomes en entrée, par exemple si tu ne prends en compte que les polynomes dont l'évaluation peut se faire en O(1) alors tu restreindras le degré des polynomes.

Tu cherches à construire un problème de NP ?

[invite3ed13054]

Oui, effectivement.