P = NP : problème ou illusion ? (partie 2)

Dans la première partie nous avons calculé la complexité de l'addition scolaire, dans le cas d'une addition à N chiffres, on a vu que l'addition scolaire était un calcul à temps linéaire, c'est à dire que le temps de calcul est proportionnel à N.

Calculons maintenant la complexité de la multiplication scolaire à N chiffres. Pour cela, nous allons prendre comme unité de temps, l'opération AxB, où A et B sont des nombres à un seul chiffre, donc :

T(AxB) = 1

Si on note A(N) et B(N) des nombres à N chiffres, calculer T(A(N)xB(N)) revient à calculer combien de multiplications "unitaires" (chiffre à chiffre) il faut réaliser pour calculer A(N)xB(N) avec la méthode scolaire.

Pour N = 2, par exemple, avec A(2) = 12 et B(2) = 34

12 * 34 = 2*4 + 10*(4*1) + 10*( 3*2 + 10*(3*1) )

Comme nous sommes en base 10, l'opération X + 10*Y revient à accoler les chiffres X et Y, en écrivant le nombre "YX", cette opération ne sera pas comptabilisé dans le calcul de la ocmplexité, on a donc :

T(A(2)xB(2)) = 4

De manière générale, pour multiplier deux nombres à N chiffres, il faudra multiplier deux à deux chaque chiffre de l'un avec ceux de l'autre, on obtient donc :

T(A(N)xB(N)) = N²

On en déduit que la multiplication scolaire est un calcul à temps quadratique : Le temps de calcul nécéssaire dépend du carré du nombre de chiffres.

De la même manière, on peut calculer le temps de calcul de n'importe quelle opération ou algorithme.

Les calculs comme l'addition ou la multiplication sont dits à temps "polynomial", car le temps dépend d'une fonction polynomiale de N (le nombre de données), c'est à dire :

T(calcul polynomial) = somme (a(k)*N^k) pour k entier

On peut donc classer l'addition et la multiplication (et un grand nombre d'autres calculs) dans l'ensemble des calculs à temps polynomiaux, on appelle cet ensemble P. (le fameux P de P = NP)

Plus précisément, l'ensemble P est appellé "Ensemble des calculs déterministes à temps polynomial", c'est à dire l'ensemble des calculs qui ne font pas appel à des fonctions aléatoires (comme l'addition ou la multiplication)

On devine donc que l'ensemble NP est tout simplement "L'Ensemble des calculs non déterministes à temps polynomial" (et non comme on le croit parfois, "L'ensemble des calculs à temps non polynomial)

Voilà pour la base... Dans la prochaine partie, nous verrons un troisième ensemble et je tenterai de donner une explication concrète du problème P = NP.

A suivre...