La preuve de la semaine

Salut à toi gentil lecteur,

Aujourd'hui je m'intéresse à la question à 1 million de dollar.
Notamment si P = NP ?

Cette question fondamentale de l'informatique méthodologique reste encore ouverte.

Dans le but de simplifier l'explication et de ne pas rentrer dans un formalisme rigoureux dépressif, nous dirons que P (polynomiale) est la classe des problèmes pour lesquels il existe des algorithmes efficaces. Alors que NP (non déterministe polynomiale) est la classe des problèmes pour lesquels il n'existe pas d'algorithmes efficaces.

Qu'est-ce que NPC
Voyons maintenant la classe NPC (NP-complet). C'est la classe des problèmes pour lesquels il est d'autant plus improbable de trouver un jour un algorithme efficace. Pour le besoin de la preuve à venir, nous définissons plus formellement la classe NPC.

Un problème L est NP-complet si:


En d'autres termes, L est dans NPC si:

1. Le problème L n'a pas d'algorithme efficace.
2. Pour tout les problèmes n'ayant pas d'algorithme efficace, il est possible de les réduire à L.
   

Et maintenant la preuve
Pour en revenir à la preuve, nous cherchons à démontrer que si NPC est dans P alors P = NP.

Nous nous donnons les hypothèses suivantes:


Trivialement nous avons:
Maintenant nous vérifions si nous avons bien:

En revenant à la définition de NPC donnée plus haut nous pouvons dire que tout langage dans NP peut être réduit en une instance de L et cela avec un algorithme dans P (efficace).
Or en s'appuyant sur l'hypothèse on sait que L est dans P. Donc si la transformation se fait efficacement et que l'algorithme pour L est efficace on peut en conclure que tout problème NP a un algorithme efficace.
Donc P = NP

Conséquences
Si P = NP alors nous aurions que des algorithmes efficaces.

Liens
La théorie de la complexité algorithmique
NP-complétude - Wikipédia