le problème P versus NP

·        Introduction

Un des problèmes du millénaire, question importante de l’informatique théorique qui se comprend en plusieurs sens :

a.     Si le fait de pouvoir vérifier un problème implique le fait de le trouver rapidement.

b.     L’intelligence peut-elle remplacer la chance ?

c.      En terme plus mathématique, si un problème NP peut-il être résolu en utilisant un algorithme ?

On voit qu’une question apparemment pouvant être résolu par un philosophe même mais la démonstration la plus plausible et acceptée sans trop de doute à l’égard de la communauté scientifique est celle à caractère scientifique.

 

·        Notion de demi-algorithme

Un demi algorithme est un algorithme exécuté sur une particularité donnée ou sur une donnée aboutissant à une portion de la solution.

La combinaison de demi-algorithmes permet de trouver une solution au problème NP complet.

 

·        Notion de schéma combinatoire

Chaque problème NP complet a son schéma combinatoire propre. Dans un cas d’un problème NP complet x ne pouvant être résolu qu’avec des demi algorithmes A, B, C, D, E alors son schéma combinatoire aboutissant à la combinaison A-E-B-D-C

Sortes des schémas combinatoires

a)    Schéma progressif : dans un schéma progressif il n’apparait pas deux ou plusieurs fois un même demi-algorithme.

 

Exemple : A-B-E-D-G-C-F, F-A-D-E-G-C-B

Dans un schéma progressif la notion de la permutation intervient pour trouver le nombre des schémas combinatoires de n demi-algorithmes.

b)    Schéma non progressif : dans ce schéma un demi-algorithme peut revenir une ou plusieurs fois sur un même schéma combinatoire

Exemple : F-A-B-A-C-G-C-F-D-B-E-D

 

·        Notion de demi-solutions

Il arrive des fois qu’une solution d’un problème NP complet soit un assemblage de plusieurs demi-solutions admettant toutes un schéma combinatoire de demi-algorithmes. Quand un problème NP-complet n’admet pas demi solution ce qu’il est simple tandis que s’il admet deux à plusieurs demi-solutions, on dit que le problème NP-complet est varié.

 

·        La notion de la difficulté du problème NP-complet

Le degré de difficulté du problème augmente lorsque le nombre de demi-solutions d’un problème NP-complet augmente aussi.

·        La solution d’un problème NP-complet varié

Pour un problème NP complet varié, il y a pour le moment la suite de demi solutions enfin d’aboutir à une solution globale, cette suite n’est pas nécessairement ordonnée, une demi solution se note par une lettre égyptienne selon ce qu’a voulu l’auteur normalement mais faute de saisie, on symbolisera par une lettre grecque.

Il est à remarquer que dans certains de problèmes NP-complet variés, dans une suite de demi-solutions et qu’il existe une demi solution centrale c’est-à-dire qui de par sa constitution complète et/ou lie les autres demi-solutions.

·        Différence entre temps de P et de NP

Dans un problème NP complet, un temps global est reparti en deux groupes de temps dont leur répartition relève de la probabilité selon qu’on a à faire face à un tel ou tel autre problème NP complet.

Un temps analytique : Est le temps nécessaire à pouvoir sculpter les schémas, les demi-solutions, … pour avoir la squelettique du problème qu’on a à faire face. En terme simple, une idée menant à la résolution, en général un canevas.

Un temps d’exécution : c’est le temps nécessaire à réaliser la solution au problème NP complet.

Il est à noter que ces deux sortes de temps ne prennent pas compte d’erreurs que peut faire le résolveur lors de deux temps.

N.B : Si l’on est face à un problème NP-complet et qu’on n’ignore d’avance comment seront la succession des éléments du problème, la probabilité de le résoudre facilement ou pas intervient. Ce principe s’applique plus aux jeux vidéo.

Il ne peut pas y avoir un problème n’usant pas de demi-algorithmes sans une solution globale.

·        Une illustration

 

Donner une illustration triviale pour permettre à tout le monde de comprendre quitte aux informaticiens théoriciens de pouvoir codifier d’avantage car le squelette central est déjà là. Nous prendrons un petit problème du jeu tétris.

Eléments : S, O1, O2, O3, T1, T2, T3, J, L, I, Z1 et Z2 (tous des tetrimino) ; le tableau tétris contient douze colonnes et dix-sept lignes équidistantes.

Demi-algorithmes : rotation à gauche, rotation à droite, un pas de case à gauche et un pas de case à droite.

Demi-solution centrale : la chute libre en bas.

Après un temps analytique x, l’heure est à la résolution.

Le résolveur se choisit S sortant de la sixième à la huitième colonne. Il lui applique cinq fois le demi-algorithme du pas d’une  case à gauche.

Le résolveur choisit T1 sortant de la sixième à la huitième colonne. Il lui applique  trois fois le demi-algorithme du pas d’une  case à gauche. Tout juste à la fin, on lui applique une fois le demi-algorithme du pas d’une  case à gauche.

Le résolveur se choisit J sortant de la septième colonne, il lui applique la rotation à droite puis une fois le demi-algorithme du pas d’une  case à gauche.

Le résolveur se choisit un O qui sort entre la septième et la huitième colonne, il lui applique une fois le demi-algorithme du pas d’une  case à gauche.

Le résolveur se choisit un deuxième O qui sort entre la septième et la huitième colonne, il lui applique aucun demi-algorithme.

Le résolveur se choisit un troisième O qui sort entre la septième et la huitième colonne, il lui applique aucun demi-algorithme.

Le résolveur se choisit un L sortant de la septième et la huitième colonne, il lui applique un demi algorithme du pas d’une case à droite.

Le résolveur se choisit Z1 compris entre la septième et la neuvième colonne, il lui applique deux fois le demi-algorithme du pas d’une case à droite.

Le résolveur se choisit Z2 compris entre la septième et la neuvième colonne, il lui applique une fois le demi-algorithme du pas d’une case à droite.

Le résolveur se choisit T2 compris entre la septième et la neuvième colonne, il lui applique le demi-algorithme de la rotation à droite puis cinq fois le demi-algorithme du pas d’une case à droite.

Ø La demi-solution qui est l’effacement de de deux lignes.

Le résolveur se choisit T3 compris entre la septième et la neuvième colonne, il lui applique quatre fois le demi-algorithme du pas d’une case à gauche.

Le résolveur se choisit T4 compris entre la septième et la neuvième colonne, il lui applique quatre fois le demi-algorithme du pas d’une case à droite.

Ø Deuxième demi-solution qui est l’effacement d’une ligne.

Ø La suite de demi-solutions complétée par la demi-solution centrale donne la solution qui est l’effacement.

 

·        Conclusion

 

L’amour du problème NP-complet est qu’il donne toujours la place à l’intelligence  humaine car c’est bien qui a conçu la machine de traitement automatique de l’information ,malgré les hautes performances de l’intelligence artificielle, robotique et informatique en général car il y a certaines des variétés des problèmes NP complet que l’informatique se bute souvent. La conclusion se voit clairement que le problème P est différent du problème NP. Pourquoi un problème P-complet se résout par un et un seul algorithme par exemple pour vérifier si une équation du second degré est vraie il suffit de connaitre une de ses racines puis appliquer l’instruction de remplacer chaque terme de x par la racine et on a la réponse il n’y a eu que le temps d’exécution. Qui dit mieux ?