P = NP : problème ou illusion ?

D'après le livre "Les énigmes mathématiques du 3ème millénaire" (Keith Devlin), le problème P = NP serait, parmi les sept, le problème le plus accessible au commun des mortels, voire, pourquoi pas, le seul problème qu'un non spécialiste pourrait éventuellement résoudre.

Etant moi-même un éminent non-spécialiste, voici ma conception de ce problème et, si on peut dire, la réponse que je pense pouvoir y apporter. Mais avant, je vais tenter de planter le décor, que signifie P = NP ?

Théorie de la complexité

La théorie de la complexité est une méthode qui permet, quel que soit le problème que l'on ait à résoudre, de calculer le temps qu'il faudra pour trouver la ou les réponses.

Plus précisément, on ne calcule pas le temps (en secondes), car cela dépend bien-sûr de la vitesse du calculateur (ordinateur ou humain), mais plutôt le nombre d'opérations simples nécéssaires pour effectuer un calcul.

Qu'est-ce qu'une opération "simple" : en fait, cela n'a pas d'importance, on pourrait prendre n'importe quelle opération comme étant "l'unité". Prenons par exemple une des opérations les plus simples qui existe : l'addition entre deux chiffres décimaux. (nombres compris entre 0 et 9)

Soient A et B deux chiffres compris entre 0 et 9, le calcul de A+B, sans retenue, nécéssite une seule opération, donc le temps T de ce problème est de 1 : T(A+B) = 1

Si l'on souhaite maintenant calculer la somme avec la retenue, il nous faut une opération supplémentaire : T(A+B+R) = 2

Combien de temps faut-il pour calculer la somme de deux nombres décimaux composés chacuns de N chiffres ?

Soient A et B deux nombres décimaux, on note A(n) le n-ième chiffre de A et B(n) celui de B (on prendra n entre 1 et n pour simplifier les formules).

Additionner A et B revient à additionner leurs chiffres respectifs, en ajoutant la retenue précédente, on notera R(n), la retenue de l'opération A(n)+B(n)+R(n-1)

A+B = (A(1)+B(1))*10^0 + (R(1)+A(2)+B(2))*10^1 + ... + (R(n-1)+A(n)+B(n))*10^(n-1) + R(n)*10^n

Autrement dit :

A+B = Somme ((A(k+1)+B(k+1)+R(k))*10^k), pour k allant de 0 à n, avec R(0)=A(n+1)=B(n+1)=0

Comme nous sommes en base 10, l'opération 10^k revient simplement à écrire les chiffres à différents emplacements (unités, dizaines, centaines...), cette partie n'entre donc pas dans le calcul de compexité de A+B.

Pour calculer T(An+Bn), il suffit de compter le nombre d'additions entre deux chiffres, dans la formule ci-dessus : chaque étape comporte 2 additions et il y a (n+1) étapes. La première et la dernière étape, ne comptent qu'une opération, on pourra donc enlever 2 au résultat final, en résumé :

T(An+Bn) = 2*(n+1) - 2 = 2*n

Cette formule signifie que le temps de calcul de l'addition de deux nombres composés de n chiffres est proportionnel à 2 fois le nombre de chiffres.

On dira que l'addition est un calcul à temps (ou à complexité) linéaire : le temps nécéssaire au calcul est proportionnel à la quantité de données en entrée, à un facteur k près. Pour l'addition de deux nombres, nous avons k = 2.

Cet indice k, représente tout simplement le nombre d'opérations nécéssaires à ajouter, à chaque fois que l'on rajoutera une donnée en entrée dans notre calcul (ici, un chiffre de plus à A et B).

Nous allons maintenant calculer la complexité de la multiplication entre deux nombres A et B composés chacuns de n chiffres décimaux : T(An*Bn)

Calculons d'abord la complexité de l'opération T(A*B), soit le cas n = 1 :

A * B = A + A + ... + A

Nous avons ici (B-1) additions, on aurait tout aussi bien pu dire (A-1). D'où :

T(A*B) = k * T(A+B), où k est une valeur qui dépend des données A et B.

A suivre ...