P = NP

La solution de cette conjecture est tirée de la formule du grand Isaac NEWTON :

$\frac{N!}{1! (N - 1)!} + \frac{N!}{2! (N - 2)!} + ... + \frac{N!}{p! (N - p)!} + ... + \frac{N!}{(N - 1)!} + \frac{N!}{N!} = 2^{N}$ .

Mais d'abord, qu'est-ce que P ? Qu'est-ce que NP ?

P =? NP est une question théorique qui concerne la complexité algorithmique des problèmes de décision.

En sortie de tout algorithme tentant de résoudre un problème de décision, la réponse attendue est soit OUI, soit NON ou encore soit VRAI soit FAUX. Il n'y a que 2 possibilités.

La difficulté de ce type de problèmes vient de ce que la solution dépend de N, le nombre des variables fournies à l'entrée de l'algorithme. Si vous avez N variables, la formule du binôme de NEWTON indique qu'il existe 2^N combinaisons de ces variables. Par conséquent, en théorie, votre algorithme devra examiner ces 2^N combinaisons.

Or, si N augmente d'une seule unité, le nombre de cas à examiner double en vertu de la formule 2^N+1 = 2 * 2^N. La croissance des cas à examiner est dite exponentielle.

La théorie de la complexité est née de cette constatation. Elle classe les problèmes en fonction de leur niveau de difficulté, en se concentrant soit sur le temps de résolution, soit sur l'espace nécessaire pour permettre la résolution du problème.

La classe P regroupe les problèmes de décision qui peuvent être résolus en temps polynomial, c'est-à-dire que l'algorithme résolvant le problème s'exécute en un temps qui est borné par un polynôme de la taille de l'entrée. La recherche d'un élément dans une liste finie ordonnée est un exemple classique d'un problème appartenant à la classe P, car il peut être résolu en temps polynomial.

La classe NP, en revanche, contient des problèmes de décision pour lesquels une solution proposée peut être vérifiée en temps polynomial.

Cependant, cela ne signifie pas nécessairement que la recherche de la solution elle-même peut être effectuée en temps polynomial.

D'où la fameuse question : peut-on trouver facilement ce que l'on peut vérifier facilement ? Autrement dit la classe de problèmes P est-elle égale à la classe de problèmes NP. ?

La réponse est positive si on transformait les problèmes de nature non déterministe en problèmes déterministes. Cela tombe sous le sens, et nous allons démontrer que cela est toujours possible.

Un problème non déterministe est caractérisé par le fait qu'à chaque étape, il existe plusieurs choix possibles, ce qui crée un arbre de solutions potentielles. Chaque feuille de cet arbre représente une solution possible au problème.

Ainsi, pour obtenir la transformation d'un problème non déterministe en un problème déterministe, l'idée est de se concentrer sur les branches de l'arbre, en examinant les combinaisons de choix possibles, partant de la racine de l'arbre à chaque feuille, d'un coup, au lieu d'explorer chaque nœud des branches de l'arbre (ce qui est coûteux en termes de temps de calcul), comme le font tous les algorithmes actuels.

En effet, dans un problème de décision, le nombre de branches est toujours connu. Il vaut toujours 2^N. C'est une donnée incontournable. Il s'agit du nombre de feuilles de l'arbre de décision. Parler ici de branches ou de feuilles est exactement la même chose parce que le nombre de chemins pour parvenir aux feuilles est égal au nombre de branches.

Et c'est là qu'intervient la célèbre formule du binôme de NEWTON.

$\frac{N!}{1! (N - 1)!} + \frac{N!}{2! (N - 2)!} + ... + \frac{N!}{p! (N - p)!} + ... + \frac{N!}{(N - 1)!} + \frac{N!}{N!} = 2^{N}$ .

Chaque constituant de la somme à gauche de la formule du binôme de NEWTON est un ensemble de combinaisons de p noeuds choisis parmi N, de cardinal $\frac{N!}{p! (N - p)!}$ . Autrement dit, chaque combinaison de l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ] est une branche contenant p noeuds.

On pressent tout de suite tous les avantages : en effet, si les p éléments de chaque combinaison sont rangés dans l'ordre lexicographique, alors les combinaisons s'ordonnent d'elles-mêmes. Voici un exemple pour p = 6 et N = 49

Cette structuration des combinaisons de p éléments choisis parmi N reste valable ∀p et ∀N, 0 < p <= N.

Bien entendu, Il n'est pas nécessaire de lister toutes les combinaisons à partir du rang 1 dès lors que l'on a établi, comme on le constate sur la figure ci-dessus, que l'ordonnancement des éléments des combinaisaons entraine l'ordonnancement de l'ensemble des combinaisons .

En regardant l'exemple de code ci-après, pour p = 6 et N = 49 et en n'oubliant pas de fixer les bornes comme je le fais, il vous sera facile de lister des plages de combinaisons que vous ferez démarrer avec le premier élément que vous voudriez et avec le nombre de combinaisons souhaitées.

Pour le code ci-dessus, valable pour des combinaisons de 6 éléments choisis parmi 49, en fixant $dep = 42 et $dep2 = 44, voici ce que vous obtiendrez :

Pour des valeurs de p et de N différentes, souvenez-vous, en générant votre code que le nombre de boucle " for" est toujours égal à p. En générant votre code pour des valeurs supérieures à 100, vous ferez moins d'erreurs.

► Notez bien que notre propre code est inspiré du code que nous vous donnons en exemple.

Vous constaterez 4 choses :

d'abord qu'il n'a pas été nécessaire de partir du rang 1.
vous pouvez faire démarrer le listage des combinaisons à partir d'un rang donné;
vous pouvez arrêter le listage des combinaisons où vous voulez
ensuite, vous n'avez pas eu besoin de mémoriser les combinaisons précédentes

En somme,vous avez gagné du temps et de l'espace.

Vous avez donc dans les mains un « oracle », cette entité hypothétique que les théoriciens de la complexité utilisent pour pouvoir finaliser leurs théories. Avec cet « oracle » vous pouvez parfaitement obtenir une plage de combinaisons ordonnées et délimitées par une borne basse et une borne haute.

Travailler avec des plages de combinaisons ordonnées vous dispense d'examiner des milliards de milliards ... milliards de milliards ... de milliards de milliards de cas.

La complexité de la transformation d'un problème non déterministe en un problème déterministe

La complexité, dans le contexte de l'informatique et de l'algorithmique, se réfère à la mesure de la quantité de ressources (telles que le temps, la mémoire ou les opérations) nécessaires pour exécuter un algorithme ou résoudre un problème informatique en fonction de la taille de l'entrée.

Elle vise à évaluer l'efficacité et les performances des algorithmes. La complexité est souvent exprimée en termes de notation (la notation O) pour indiquer comment le temps ou l'espace requis augmente à mesure que la taille de l'entrée augmente. Voici un tableau qui illustre ce concept :

Avec des factorielles d'un côté et une exponentielle de l'autre, la formule du binôme de NEWTON pour N = 1000 semble être impraticable :

$\frac{N!}{1! (N - 1)!} + \frac{N!}{2! (N - 2)!} + ... + \frac{N!}{p! (N - p)!} + ... + \frac{N!}{(N - 1)!} + \frac{N!}{N!} = 2^{N}$ .

Or, comme nous l'avons observé précédemment, la formule du binôme de NEWTON, dans sa partie gauche n'est rien d'autre qu'une liste finie de combinaisons que l'on peut facilement transformée en une liste finie ordonnée de combinaisons.
L'ordonnancement des combinaisons change radicalement la donne.

Complexité de la recherche de k éléments, k <= p, dans une combinaison dont les éléments sont ordonnés :

La complexité de la recherche de k éléments dans une combinaison ordonnée de p éléments choisis parmi N, les p éléments étant ordonnés selon l'ordre lexicographique, se fera en k * log₂(p) opérations (recherche dichotomique).

Complexité de la recherche de k éléments, k <= p, d'une combinaison dans l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ] :

La complexité de la recherche de k éléments d'une combinaison ordonnée de p éléments choisis parmi N, dans la liste ordonnée des combinaisons de l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ], s'effectuera en k * log₂(p) * log₂( $\frac{N!}{p! (N - p)!}$ ) opérations (Recherche dichotomique).

Complexité de la recherche d'une combinaison de k éléments, k <= p dans l'intervalle |1,2^N]:

Prenons d'abord l'exemple de N = 10, ce qui nous donne l'intervalle [1, 1024 = 2¹⁰]. Une image valant mieux que tous les discours, voici la numérotation des combinaisons

La numérotation des combinaisons dans l'intervalle [1, 2^N] est croissante et unique.

La complexité de la recherche de k éléments d'une combinaison ordonnée de p éléments choisis parmi N dans la liste ordonnée des combinaisons de l'intervalle [1, 2^N] s'effectuera en N * k * log₂(p) * log₂( $\frac{N!}{p! (N - p)!}$ ) opérations.

Peut-on alors trouver facilement ce que l'on peut vérifier facilement ?

Nous avons montré qu'il existe une bijection entre l'ensemble des entiers de l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ] et l'ensemble des combinaisons de cardinal $\frac{N!}{p! (N - p)!}$ . Il s'agit d'un ordre local

Dans cet ensemble muni d'un ordre local, on peut toujours non seulement identifier une combinaison désignée par son rang r₁, r₁ pris dans l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ], mais aussi faire l'inverse, c'est à dire trouver le rang de la combinaison dans l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ] à partir de la combinaison elle-même.

Pour cela, dans l'intervalle [1, $\frac{N!}{p! (N - p)!}$ ] nous avons conçu 2 fonctions :

rang₁ = coder₁(combinaison₁), (en somme : y = f(x) );
combinaison₁ = decoder₁(rang₁), (en somme : x = f(y) ).

Nous avons montré qu'il existe aussi un ordre global des combinaisons dans l'intervalle [1, 2^N]. Par conséquent, nous avons conçu également 2 autres fonctions permettant d'explorer cet intervalle :

rang₂ = coder₂(combinaison₂)
combinaison₂ = decoder₂(rang₂)

Avec les ordres de complexité donnés, on peut donc affirmer que l'on peut trouver facilement ce que l'on peut vérifier facilement.

Application concrète de l'algorithme à un problème typiquement SAT

Sur le site du CLAY MATHEMATIC INSTITUTE, Stephen COOK, l'un des auteurs de la théorie de la complexité, évoque, dans la présentation de la conjecture P = NP, le problème suivant :

Supposons que vous organisiez l'hébergement d'un groupe de quatre cents étudiants. L'espace est limité et seulement une centaine d'étudiants pourront être héberbergés dans le dortoir. Pour compliquer les choses, le doyen vous a fourni une liste de paires d'étudiants incompatibles, et a demandé qu'aucune paire de cette liste n'apparaisse dans votre choix final.

La difficulté, selon COOK -- et son propos est partagé par l'ensemble de la communauté scientifique -- est la suivante :

le nombre total de façons de choisir cent étudiants parmi les quatre cents candidats est plus élevé que le nombre d'atomes dans l'univers connu. Ainsi, aucune civilisation future ne pourrait jamais espérer construire un superordinateur capable de résoudre le problème par la force brute, c'est-à-dire en vérifiant toutes les combinaisons possibles de 100 étudiants

Cook précise toutefois :

Cependant, cette apparente difficulté ne peut que refléter le manque d’ingéniosité de votre programmeur.

Ce problème d"hébergement, avec ses contraintes, peut être formalisé comme une instance de SAT, parce que nous avons :

des variables booléennes représentant l'affectation des étudiants aux places dans le dortoir;
des clauses représentant les paires d'étudiants incompatibles;
la question de savoir si l'on peut vérifier en temps polynomial si une affectation d'un groupe proposé de 100 étudiants choisis parmi 400 satisfait la contrainte de compatibilité.

Toute les conditions d'un problème SAT sont donc réunies.

► Notez bien que, si à la place du mot « étudiants », on substitue les mots : « hypothèses », « molécules » , « situations » .... l'algorithme de résolution s'appliquera de la même façon à tout ensemble d'entités où des contraintes d'incompatibilité doivent être respectées lors de l'affectation ou de la combinaison de ces entités.

► Notez également que pour p = 100 et N = 400, le nombre de combinaisons est égal à $\frac{400!}{100! (400 - 100)!}$ = 2 241 854 791 554 337 561 923 210 387 201 698 554 845 411 177 476 295 990 399 942 258 896 013 007 429 693 894 018 935 107 174 320

Ce nombre s'écrit avec 97 chiffres, et est de l'ordre de 2³²². Par comparaison, le nombre estimé d'atomes dans l'univers observable, selon les physiciens, serait de l'ordre de 10⁸⁰ soit environ 2²⁶⁶.

Malgré le gigantisme de ces chiffres, l'objectif est donc non seulement de dénombrer, à partir d'une liste donnée d'éléments incompatibles, les ensembles de combinaisons d'éléments qui satisfont la contrainte de compatibilité, mais encore de pouvoir les identifier, une par une, pour que l'on puisse vérifier, à la demande, si la contrainte de compatibilité est satisfaite ou non par les combinaisons proposées.

Mieux encore, vu leur nombre, nous vous livrerons autant de combinaisons que vous souhaiterez ... d'une manière instantanée, à partir d'un simple PC, alors que cette réalisation est considérée comme impossible en faisant tourner des supercalculateurs pendant des siècles.

Données en entrée. Comme dans tout problème SAT, nous avons :

une liste des variables booléennes, que nous noterons : e₁, e₂ ... e_i ... e₃₉₉, e₄₀₀. (Mais pour des raisons de simplicité, on utilisera les indices : 1,2 ...400 plutôt que la notation e_i).

une liste de clauses, ici la liste des paires d'étudiants dont la cohabitation est jugée incompatible, par exemple :

{22,94}, {6,394}, {7,48}, {10,337}, {13,224}, {13,246}, {17,29}, {17,254}, {18,302}, {21,295}, {22,71}, {24,160}, {28,128}, {33,53}, {33,250}, {36,107}, {36,230}, {42,244}, {42,57}, {44,25}, {45,55}, {49,82}, {50,196}, {54,12}, {59,22}, {59,76}, {61,112}, {63,342}, {65,72}, {67,42}, {67,248}, {69,156}, {70,289}, {71,51}, {71,159}, {75,115}, {76,148}, {76,171}, {76,198}, {77,295}, {77,56}, {80,163}, {84,284}, {87,42}, {94,48}, {96,270}, {97,367}, {97,177}, {99,267}, {101,116}, {102,90}, {103,245}, {108,169}, {108,306}, {108,79}, {108,83}, {113,215}, {116,269}, {117,173}, {118,133}, {121,280}, {127,48}, {129,314}, {131,269}, {132,170}, {136,243}, {138,312}, {139,60}, {139,178}, {145,20}, {146,305}, {149,79}, {151,86}, {154,233}, {157,269}, {162,179}, {163,328}, {167,393}, {167,82}, {169,38}, {170,125}, {170,258}, {173,330}, {175,333}, {176,211}, {177,8}, {183,350}, {183,265}, {184,393}, {184,308}, {185,170}, {187,259}, {189,14}, {189,61}, {192,256}, {193,48}, {196,136}, {196,77}, {199,360}, {206,354}, {207,377}, {209,39}, {209,397}, {210,212}, {211,167}, {211,192}, {212,262}, {213,130}, {214,36}, {214,178}, {218,259}, {218,288}, {219,377}, {221,252}, {224,342}, {226,256}, {229,21}, {230,338}, {233,216}, {233,326}, {234,43}, {234,105}, {235,62}, {236,90}, {238,9}, {239,188}, {241,155}, {243,180}, {245,396}, {247,106}, {251,309}, {254,378}, {255,13}, {255,383}, {258,151}, {259,272}, {263,251}, {264,207}, {264,292}, {265,166}, {265,132}, {267,216}, {267,338}, {270,3}, {271,198}, {273,219}, {273,282}, {275,144}, {278,280}, {278,27}, {278,200}, {279,267}, {279,38}, {287,387}, {289,60}, {292,138}, {295,158}, {295,234}, {295,25}, {297,208}, {299,330}, {308,140}, {308,159}, {308,67}, {308,233}, {312,169}, {314,205}, {316,380}, {316,127}, {320,182}, {321,91}, {323,302}, {327,104}, {329,172}, {330,393}, {333,321}, {337,333}, {338,84}, {340,224}, {341,350}, {344,194}, {344,374}, {345,396}, {345,194}, {348,106}, {352,396}, {353,268}, {355,156}, {356,393}, {363,352}, {371,232}, {372,279}, {372,291}, {373,389}, {376,258}, {376,121}, {379,33}, {381,368}, {389,260}, {394,344}, {400,68}

La liste donnée est constituée de 201 paires d'incompatibles; donc de 201 clauses si on utilise la terminologie utilisée dans SAT.

Données attendues en sortie

Des listes de combinaisons de 100 étudiants choisis parmi 400 ne contenant aucune paire d'incompatibles.

Méthodologie de résolution

Tenter de trouver une assignation de valeurs de vérité aux variables qui rende une formule booléenne vraie, pour n = 400 et avec 201 clauses, avec des algorithmes comme DPLL (Davis–Putnam–Logemann–Loveland), ou APT (Aspvall, Plass et Tarjan) ou des solveurs de type CDCL (Conflict-Driven Clause Learning) est voué à l'echec, tant l'intervalle de solutions est incommensurablement vaste !

Notre approche, est donc radicalement différente.

Plutôt que de nous concentrer directement sur l'assignation de valeurs de vérité aux variables pour rendre la formule booléenne vraie, notre méthode commence par une analyse plus approfondie des clauses, identifiant les paires d'éléments incompatibles dans ces clauses.

En effet, dans une liste de clauses, on peut toujours organiser les variables en paires de variables incompatibles en identifiant les relations de compatibilité et d'incompatibilité entre elles. Chaque variable peut être soit compatible avec toutes les autres, soit incompatible avec au moins une autre.

L'organisation des variables en paires de variables incompatibles peut se faire sur un tableau de taille n lignes et de n colonnes. Par exemple, si n = 3, le tableau pourrait ressembler à ceci :

Dans cet exemple, × indique l'incompatibilité entre les variables correspondantes, et "-" indique la compatibilité. Chaque ligne ou colonne représente une variable, et les entrées du tableau indiquent si les variables correspondantes sont compatibles ou incompatibles.

En raisonnant sur les indices plutôt que sur les variables elles-mêmes, on simplifie et on rend l'analyse numérique plus rapide et plus évidente. Avec l'exemple donné, on a les clauses suivantes : {1, 2}, {1, 3}, {2,3} toutes réduites à des clauses de taille 2.

La réduction des clauses à des listes de clauses de taille 2 est utilisée dans l'algorithme APT et n'est donc pas une nouveauté dans un processus de résolution du problème SAT

Cette représentation par les indices facilite l'analyse des relations d'incompatibilité entre les variables et sera utilisée pour guider le processus de résolution du problème SAT d'une manière plus structurée.

En effet, puisque la liste des incompatibles est organisée par paires, si les incompatibles ne sont pas triés, il faut alors les trier de façon à ce que la valeur des indices des premiers éléments de chaque paire soit inférieure à la valeur des indices des seconds. En ordonnant les paires de cette façon par leurs indices, nous avons ordonné la liste des incompatibles elle-même.

Il est alors possible de déterminer deux groupes :

le groupe A: constitué des éléments incompatibles avec au moins un autre
le groupe B: formé par les éléments tous compatibles.

Par construction, le groupe A et le groupe B sont réciproquement complémentaires l'un de l'autre.

La seconde étape consiste à séparer le groupe A en deux sous groupes :

le groupe X_A1, composé des premiers éléments des paires d'éléments du groupe A, en évitant les doublons
le groupe X_A2, composé des seconds éléments des paires d'éléments du groupe A, en évitant les doublons

Ainsi, par construction également, les éléments des groupes X_A1 et X_A2 sont composés d'éléments tous compatibles entre eux

Voici une illustration de la construction des groupes X_A1 et X_A2 Considérons par exemple, les paires suivantes qui sont toutes des clauses de taille 2 : {22, 59}, {22, 71}, {22, 94}, ... {59, 76} ... {76, 148}, {76, 171} et {76, 198}.... {198, 271}.

Comme la liste des paires est ordonnée sur le premier élément de la paire, puis par le second élément, lorsqu'on arrive à l'élément 22 de la paire {22, 59}, s'il n'est pas dans la liste X_A2., c'est à dire s'il n'a jamais figuré comme second élément d'une paire d'incompatibles, on peut l'ajouter directement dans la liste X_A1 ...s'il n'est pas déjà dans cette liste, bien entendu.

Ensuite, on ajoute l'élément 59 à la liste X_A2.s'il n'y est pas déjà. Lorsque l'on traitera les 2 autres paires {22, 71} et {22, 94}, le premier élément 22 ne sera jamais ajouté à la liste X_A1 puisqu'il y est déjà enregistré. En revanche, si les éléments 71 et 94 ne figurent pas déjà dans la liste X_A2, ils y seront ajoutés.

Lorsqu'on vient à examiner la paire {59, 76}, où 59 est le premier élément de la paire, on vérifie d'abord s'il n'est pas déja enregistré dans la liste X_A2.Comme tel est le cas, on ne fait rien. En revanche, si le second élément de la paire, ici l'élément 76, n'existe pas dans la liste X_A2, on l'y ajoute.

La situation va se renouveler avec l'élément 76 qui se trouve être incompatible avec 3 autres éléments : {76, 148}, {76, 171} et {76, 198}. Le processus de tri et d'enregistrement est strictement le même que celui décrit précédement.

Il en sera de même avec la paire d'incompatibles {198, 271}.

La complexité de ce processus de séparation est réduite à la taille de la liste du groupe A.

Maintenant que nous avons constitué les deux groupes X_A1 et X_A2, contenant chacun des éléments tous compatibles entre eux, nous pouvons, sachant que tous les éléments du groupe B sont compatibles entre eux et complémentaires du groupe A :

ajouter au groupe X_A1 tois les éléments du groupe B pour former le groupe X_B1 de cardinal C₁, tous compatibles entre eux;
ajouter au groupe X_A2 tois les éléments du groupe B pour former le groupe X_B2 de cardinal C₂, tous compatibles entre eux.

Si chaque cardinal, C₁ et C₂ sont supérieurs à p variables jugés nécessaires pour la réalisation d'un objectif, on aura respectivement C(C₁,p) et C(C₁,p) combinaisons d'éléments tous compatibles entre eux.

Les éléments de ces combinaisons sont des pointeurs sur les combinaisons des groupes X_B1 et X_B2.

***********************

Application au problème d'hébergement exposé par Stephen COOK

***********************

Reprenons la liste de 201 paires d'incompatibles qui nous avait été fournie précédemment :

Trions cette liste selon la valeur de l'indice du 1^er élément puis, le cas échéant, suivant la valeur de l'indice du second :
3, 270; 6, 394; 7, 48; 8, 177; 9, 238; 10, 337; 12, 54; 13, 224; 13, 246; 13, 255; 14, 189; 17, 29; 17, 254; 18, 302; 20, 145; 21, 229; 21, 295; 22, 59; 22, 71; 22, 94; 24, 160; 25, 44; 25, 295; 27, 278; 28, 128; 33, 53; 33, 250; 33, 379; 36, 107; 36, 214; 36, 230; 38, 169; 38, 279; 39, 209; 42, 57; 42, 67; 42, 87; 42, 244; 43, 234; 45, 55; 48, 94; 48, 127; 48, 193; 49, 82; 50, 196; 51, 71; 56, 77; 59, 76; 60, 139; 60, 289; 61, 112; 61, 189; 62, 235; 63, 342; 65, 72; 67, 248; 67, 308; 68, 400; 69, 156; 70, 289; 71, 159; 75, 115; 76, 148; 76, 171; 76, 198; 77, 196; 77, 295; 79, 108; 79, 149; 80, 163; 82, 167; 83, 108; 84, 284; 84, 338; 86, 151; 90, 102; 90, 236; 91, 321; 96, 270; 97, 177; 97, 367; 99, 267; 101, 116; 103, 245; 104, 327; 105, 234; 106, 247; 106, 348; 108, 169; 108, 306; 113, 215; 116, 269; 117, 173; 118, 133; 121, 280; 121, 376; 125, 170; 127, 316; 129, 314; 130, 213; 131, 269; 132, 170; 132, 265; 136, 196; 136, 243; 138, 292; 138, 312; 139, 178; 140, 308; 144, 275; 146, 305; 151, 258; 154, 233; 155, 241; 156, 355; 157, 269; 158, 295; 159, 308; 162, 179; 163, 328; 166, 265; 167, 211; 167, 393; 169, 312; 170, 185; 170, 258; 172, 329; 173, 330; 175, 333; 176, 211; 178, 214; 180, 243; 182, 320; 183, 265; 183, 350; 184, 308; 184, 393; 187, 259; 188, 239; 192, 211; 192, 256; 194, 344; 194, 345; 198, 271; 199, 360; 200, 278; 205, 314; 206, 354; 207, 264; 207, 377; 208, 297; 209, 397; 210, 212; 212, 262; 216, 233; 216, 267; 218, 259; 218, 288; 219, 273; 219, 377; 221, 252; 224, 340; 224, 342; 226, 256; 230, 338; 232, 371; 233, 308; 233, 326; 234, 295; 245, 396; 251, 263; 251, 309; 254, 378; 255, 383; 258, 376; 259, 272; 260, 389; 264, 292; 267, 279; 267, 338; 268, 353; 273, 282; 278, 280; 279, 372; 287, 387; 291, 372; 299, 330; 302, 323; 316, 380; 321, 333; 330, 393; 333, 337; 341, 350; 344, 374; 344, 394; 345, 396; 352, 363; 352, 396; 356, 393; 368, 381; 373, 389;

Le tri précédent nous a permis de constituter le groupe A, constitué de 253 éléments incompatibles avec au moins un autre. Certains le sont avec plusieurs:
3, 6, 7, 8, 9, 10, 12, 13, 14, 17, 18, 20, 21, 22, 24, 25, 27, 28, 29, 33, 36, 38, 39, 42, 43, 44, 45, 48, 49, 50, 51, 53, 54, 55, 56, 57, 59, 60, 61, 62, 63, 65, 67, 68, 69, 70, 71, 72, 75, 76, 77, 79, 80, 82, 83, 84, 86, 87, 90, 91, 94, 96, 97, 99, 101, 102, 103, 104, 105, 106, 107, 108, 112, 113, 115, 116, 117, 118, 121, 125, 127, 128, 129, 130, 131, 132, 133, 136, 138, 139, 140, 144, 145, 146, 148, 149, 151, 154, 155, 156, 157, 158, 159, 160, 162, 163, 166, 167, 169, 170, 171, 172, 173, 175, 176, 177, 178, 179, 180, 182, 183, 184, 185, 187, 188, 189, 192, 193, 194, 196, 198, 199, 200, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 218, 219, 221, 224, 226, 229, 230, 232, 233, 234, 235, 236, 238, 239, 241, 243, 244, 245, 246, 247, 248, 250, 251, 252, 254, 255, 256, 258, 259, 260, 262, 263, 264, 265, 267, 268, 269, 270, 271, 272, 273, 275, 278, 279, 280, 282, 284, 287, 288, 289, 291, 292, 295, 297, 299, 302, 305, 306, 308, 309, 312, 314, 316, 320, 321, 323, 326, 327, 328, 329, 330, 333, 337, 338, 340, 341, 342, 344, 345, 348, 350, 352, 353, 354, 355, 356, 360, 363, 367, 368, 371, 372, 373, 374, 376, 377, 378, 379, 380, 381, 383, 387, 389, 393, 394, 396, 397, 400

La constitution du groupe A nous permet de déterminer le groupe B, complémentaire du groupe A. Il est donc constitué de 147 éléments, tous compatibles entre eux:
1, 2, 4, 5, 11, 15, 16, 19, 23, 26, 30, 31, 32, 34, 35, 37, 40, 41, 46, 47, 52, 58, 64, 66, 73, 74, 78, 81, 85, 88, 89, 92, 93, 95, 98, 100, 109, 110, 111, 114, 119, 120, 122, 123, 124, 126, 134, 135, 137, 141, 142, 143, 147, 150, 152, 153, 161, 164, 165, 168, 174, 181, 186, 190, 191, 195, 197, 201, 202, 203, 204, 217, 220, 222, 223, 225, 227, 228, 231, 237, 240, 242, 249, 253, 257, 261, 266, 274, 276, 277, 281, 283, 285, 286, 290, 293, 294, 296, 298, 300, 301, 303, 304, 307, 310, 311, 313, 315, 317, 318, 319, 322, 324, 325, 331, 332, 334, 335, 336, 339, 343, 346, 347, 349, 351, 357, 358, 359, 361, 362, 364, 365, 366, 369, 370, 375, 382, 384, 385, 386, 388, 390, 391, 392, 395, 398, 399

Comme le nombre d'éléments du groupe B est supérieur à p = 100, on peut donc former

\frac{147!}{100! (147 - 100)!}

= 715 620 812 317 696 123 647 938 679 242 181 368 880 combinaisons de 100 étudiants choisis parmi ces 147, tous parfaitement compatibles entre eux.

Malgré la proportion infinitésimale des éléments tous compatibles du groupe B, qui est de l'ordre de 3,19.10^-53% par rapport à l'ensemble des combinaisons de 100 étudiants parmi 400, en formant le groupe B, nos deux fonctions coder₁ et decoder₁ permettent :

d'identifier l'ensemble des combinaisons de ce groupe, , de cardinal $\frac{147!}{100! (147 - 100)!}$
de les interroger, une par une, séquentiellement, ou au hasard pour vérifier en temps polynomial que la contrainte de compatibilité est bien respectée;
déterminer l'emplacement de chacune des combinaisons, donc son rang
1. r₁ dans l'intervalle [1, $\frac{400!}{100! (400 - 100)!}$ ],
2. r₂ dans l'intervalle [1, 2⁴⁰⁰],

Le résultat obtenu est similaire à l'identification d'un atome particulier dans l'univers observable ... et même un peu au-delà !

Voici par exemple un rang r₀ choisi au hasard dans l'intervalle [1, $\frac{147!}{100! (147 - 100)!}$ ] :

361 362 776 168 645 814 601 693 079 519 499 583 442

La fonction decoder₁ nous a renvoyé la combinaison de 100 éléments choisis parmi 147 suivante :

1, 3, 4, 5, 6, 9, 10, 12, 14, 15, 16, 17, 19, 20, 21, 23, 24, 25, 27, 28, 29, 30, 33, 34, 35, 37, 38, 39, 40, 44, 46, 48, 50, 52, 53, 54, 55, 56, 58, 61, 62, 64, 65, 66, 67, 68, 70, 71, 75, 76, 78, 79, 81, 82, 84, 86, 88, 89, 90, 91, 92, 94, 96, 97, 99, 100, 101, 102, 103, 104, 105, 106, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 123, 124, 125, 126, 127, 128, 132, 136, 137, 138, 139, 142, 143, 144, 145, 146, 147

Chaque élément de la combinaison X_A1 pointe sur le contenu d'une cellule du groupe B, ce qui nous donne la combinaison suivante du groupe X_B1, composée d'éléments tous compatibles entre eux :

1, 4, 5, 11, 15, 23, 26, 31, 34, 35, 37, 40, 46, 47, 52, 64, 66, 73, 78, 81, 85, 88, 93, 95, 98, 109, 110, 111, 114, 123, 126, 135, 141, 143, 147, 150, 152, 153, 164, 174, 181, 190, 191, 195, 197, 201, 203, 204, 223, 225, 228, 231, 240, 242, 253, 261, 274, 276, 277, 281, 283, 286, 293, 294, 298, 300, 301, 303, 304, 307, 310, 311, 315, 317, 318, 319, 324, 325, 331, 332, 334, 335, 336, 347, 349, 351, 357, 358, 359, 365, 375, 382, 384, 385, 390, 391, 392, 395, 398, 399

Sans aucune machine, à la main, vous pouvez vérifier que, par rapport à la liste fournie d'incompatibles, constituée de 201 clauses, la combinaison fournie en sortie de l'algorithme ne contient aucune paire d'éléments incompatibles.

En fournissant cette combinaison d'éléments tous compatibles à notre fonction decoder₁, elle nous renvoie son rang r₁ dans l'intervalle [1, $\frac{400!}{100! (400 - 100)!}$ ] :

680 842 114 332 546 883 636 652 588 285 900 398 719 940 156 010 102 445 001 268 192 860 096 999 463 272 213 898 574 641 288 308

La fonction decoder₂, quant à elle, nous renvoie le rang r₂ de la combinaison dans l'intervalle [1, 2⁴⁰⁰].

1 180 205 221 990 928 401 130 940 632 243 546 437 113 387 428 671 517 384 499 339 236 407 893 665 643 116 010 340 569 013 716 037

A ce stade, nous pouvons observer

Qu'aucune machine quantique, aucun algorithme d'intelligence artificielle n'est capable de fournir un résultat aussi précis.
Par ailleurs, il suffit
1. d'augmenter le rang des combinaisons d'index pour obtenir les prochaines combinaisons d'éléments tous compatibles.
2. diminuer le rang des combinaisons d'index pour obtenir les précédentes combinaisons d'éléments tous compatibles

***********************

Livraison des combinaisons «X_B1» et «X_B2»

***********************

Dans la section précédente, à partir d'une liste donnée d'élémements incompatibles, nous avons séparé le groupe de 400 éléments en deux sous-groupes :

D'une part, le groupe A, formé par les éléments qui sont incompatibles avec au moins un élément; ils sont au nombre de 253;
D'autre part, le groupe B, composé de tous les éléments compatibles entre eux. On en a dénombré 147.

Ensuite, nous avons montré comment nous pouvons identifier chacune des combinaisons du groupe B dans les intervalles [1, $\frac{400!}{100! (400 - 100)!}$ ] et [1, 2⁴⁰⁰] avec nos fonctions.

Mais la solution, même si elle remplit le contrat, qui est de fournir des listes d'éléments « tous compatibles », n'est ni complète ni équitable puisque nous avons écarté d'office de notre proposition les 253 éléments incompatibles avec au moins un autre, sans l'être avec tous les autres.

Nous allons donc corriger cette situation dans la section suivante et permettre à tous les étudiants d'avoir la possibilité d'être choisis.

Constitution des groupes X_A1 et X_A2

Après séparation du groupe A selon la méthode décrite précédemment, nous avons obtenu le groupe X_A1, composé des premiers éléments des paires de la liste des incompatibles. Ce groupe est constitué de 113 éléments tous compatibles entre eux.
3, 6, 7, 8, 9, 10, 12, 13, 14, 17, 18, 20, 21, 22, 24, 25, 27, 28, 33, 36, 38, 39, 42, 43, 45, 49, 50, 51, 56, 60, 61, 62, 63, 65, 67, 68, 69, 70, 75, 79, 80, 83, 84, 86, 90, 91, 96, 97, 99, 101, 103, 104, 105, 106, 113, 117, 118, 121, 125, 129, 130, 131, 132, 136, 138, 140, 144, 146, 154, 155, 157, 158, 162, 166, 172, 175, 176, 180, 182, 183, 184, 187, 188, 192, 194, 199, 200, 205, 206, 207, 208, 210, 216, 218, 219, 221, 226, 230, 232, 251, 254, 255, 260, 268, 287, 291, 299, 341, 345, 352, 356, 368, 373

Le groupe X_A2 est constitué de 128 éléments tous compatibles entre eux :
29, 44, 48, 53, 54, 55, 57, 59, 71, 72, 76, 77, 82, 94, 102, 107, 108, 112, 115, 116, 127, 128, 133, 139, 145, 148, 151, 156, 159, 160, 163, 167, 169, 170, 171, 173, 177, 178, 179, 185, 189, 193, 196, 198, 209, 211, 212, 213, 214, 215, 224, 229, 233, 234, 235, 238, 239, 241, 243, 245, 247, 248, 252, 256, 258, 259, 262, 263, 264, 265, 267, 269, 270, 271, 272, 273, 275, 278, 279, 280, 282, 284, 289, 292, 295, 297, 302, 305, 306, 308, 312, 314, 316, 320, 321, 323, 326, 327, 328, 329, 330, 333, 337, 338, 340, 342, 344, 350, 353, 354, 355, 360, 363, 371, 372, 374, 376, 378, 380, 381, 383, 387, 389, 393, 394, 396, 397, 400

Le groupe X_B1 est la fusion ensuite du groupe B, composé de 147 éléments intrinsèquement tous compatibles entre eux et du groupe X_A1 débarrassé de tous les éléments avec lesquels ils sont incompatibles, et qui est composé de 113 éléments
Au total, le groupe X_B1 est donc composé de 260 éléments tous compatibles entre eux
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 49, 50, 51, 52, 56, 58, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 73, 74, 75, 78, 79, 80, 81, 83, 84, 85, 86, 88, 89, 90, 91, 92, 93, 95, 96, 97, 98, 99, 100, 101, 103, 104, 105, 106, 109, 110, 111, 113, 114, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 129, 130, 131, 132, 134, 135, 136, 137, 138, 140, 141, 142, 143, 144, 146, 147, 150, 152, 153, 154, 155, 157, 158, 161, 162, 164, 165, 166, 168, 172, 174, 175, 176, 180, 181, 182, 183, 184, 186, 187, 188, 190, 191, 192, 194, 195, 197, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 210, 216, 217, 218, 219, 220, 221, 222, 223, 225, 226, 227, 228, 230, 231, 232, 237, 240, 242, 249, 251, 253, 254, 255, 257, 260, 261, 266, 268, 274, 276, 277, 281, 283, 285, 286, 287, 290, 291, 293, 294, 296, 298, 299, 300, 301, 303, 304, 307, 310, 311, 313, 315, 317, 318, 319, 322, 324, 325, 331, 332, 334, 335, 336, 339, 341, 343, 345, 346, 347, 349, 351, 352, 356, 357, 358, 359, 361, 362, 364, 365, 366, 368, 369, 370, 373, 375, 382, 384, 385, 386, 388, 390, 391, 392, 395, 398, 399

Le groupe X_B1 est constitué de $\frac{260!}{100! (260 - 100)!}$ combinaisons qui remplissent la contrainte tous compatibles. Chacune de ces combinaisons peut être identifiée et vérifiée.

Le groupe X_B2 est la fusion également du groupe B, composé de 147 éléments intrinsèquement tous compatibles entre eux et du groupe X_A2 débarrassé de tous les éléments avec lesquels ils sont incompatibles, et qui est composé de 128 éléments
Au total le groupe X_B2 est composé de 275 éléments tous compatibles entre eux
1, 2, 4, 5, 11, 15, 16, 19, 23, 26, 29, 30, 31, 32, 34, 35, 37, 40, 41, 44, 46, 47, 48, 52, 53, 54, 55, 57, 58, 59, 64, 66, 71, 72, 73, 74, 76, 77, 78, 81, 82, 85, 88, 89, 92, 93, 94, 95, 98, 100, 102, 107, 108, 109, 110, 111, 112, 114, 115, 116, 119, 120, 122, 123, 124, 126, 127, 128, 133, 134, 135, 137, 139, 141, 142, 143, 145, 147, 148, 150, 151, 152, 153, 156, 159, 160, 161, 163, 164, 165, 167, 168, 169, 170, 171, 173, 174, 177, 178, 179, 181, 185, 186, 189, 190, 191, 193, 195, 196, 197, 198, 201, 202, 203, 204, 209, 211, 212, 213, 214, 215, 217, 220, 222, 223, 224, 225, 227, 228, 229, 231, 233, 234, 235, 237, 238, 239, 240, 241, 242, 243, 245, 247, 248, 249, 252, 253, 256, 257, 258, 259, 261, 262, 263, 264, 265, 266, 267, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 289, 290, 292, 293, 294, 295, 296, 297, 298, 300, 301, 302, 303, 304, 305, 306, 307, 308, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 342, 343, 344, 346, 347, 349, 350, 351, 353, 354, 355, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 369, 370, 371, 372, 374, 375, 376, 378, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400

Le groupe X_B2 est constitué de $\frac{275!}{100! (275 - 100)!}$ combinaisons qui remplissent la contrainte tous compatibles. Chacune de ces combinaisons peut être identifiée et vérifiée.

Conclusion

***********************

On peut vérifier à, même la main, qu'aucun élément des groupes X_B1 et X_B2 n'est incompatible avec un autre élément de son groupe.

Par suite, toute combinaison de X_B1 et de X_B2 pointée respectivement par une combinaison de l'intervalle [1, $\frac{260!}{100! (260 - 100)!}$ ] et de l'intervalle [1, $\frac{275!}{100! (275 - 100)!}$ ] ne contient que des éléments compatibles entre eux;

► Vous noterez que, à aucun moment, nous avons perdu notre temps à chercher à assigner une valeur de vérité à chaque variable. Notre méthode consiste à prendre des variables, lesquelles regroupées en ensemble dont les parties forment naturellement des clauses où tous les éléments sont compatibles entre eux.

Autrement dit, lorsque vous prenez n'importe quelle combinaison des groupes formées selon la méthode expliquée, la combinaison de ces variables forme une propostion logique dont la valeur de vérité est toujours VRAI.

CQFD.

Au total, avec la liste donnée de 201 paires d'étudiants dont la cohabitation est jugée incompatible, nous pouvons former $\frac{260!}{100! (260 - 100)!}$ + $\frac{275!}{100! (275 - 100)!}$ combinaisons d'étudiants tous compatibles entre eux, chacune d'elle identifiable en temps polynomial (quelques micro-secondes sur un PC doté de 8 Go de RAM avec un algorithme écrit en php) et dont le contrôle peut être effectué également en temps polynomial (même à la main en réalité)

Ce problème, de type SAT, réputé irréalisable depuis 50 ans, ne pose en réalité aucune difficulté.

La preuve est donc faite de ce que l'on peut trouver facilement ce que l'on peut vérifier facilement. Autrement dit, nous avons la preuve de ce que P = NP.

Cet exemple anticipe sur la description de la résolution du problème SAT mais il est nécessaire pour que vous puissiez comprendre l'utilité de travailler sur des plages de combinaisons.

Supposons en effet que vous devez choisir 100 éléments parmi une liste de 400 éléments et que l'on vous impose la clause suivante : la paire d'éléments numérotés respectivement 24 et 92 sont incompatibles. Sur cette base, vous devez fournir :

les plages de combinaisons contenant 24 et jamais 92, ce qui détermine le nombre de combinaisons satisfaisant cette contrainte
idem pour les plages contenant 92 et jamais 24.
idem également pour les plages ne contenant ni 24 ni 92

Aucune intelligence artificielle actuelle et aucune machine quantique ne seraient capables de vous donner un résultat que nous allons pourtant vous fournir en moins d'une seconde.

Le procédé pour obtenir toutes les plages contenant 24 mais jamais 92 est le suivant:

Si je veux éliminer le numéro 92, il me suffit de l’écraser en formant le bloc {91,93}. Ensuite, je calcule le rang de la combinaison ainsi obtenue. Elle sera la borne basse de ma plage de combinaisons

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 96, 97, 98, 99, 100, 101, dont le rang est 1832649 805164487

Je calcule ensuite la borne haute (tous les éléments après 93 doivent avoir leurs valeurs maximales … ici sans jamais dépasser 400 en position finale, donc en position 100

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 393, 394, 395, 396, 397, 398, 399, 400, dont le rang est 3617698 316688336

Le nombre de combinaisons contenant 24 mais jamais 92 dans cette plage s’obtient par la différence entre la borne haute et la borne basse est égale à Haut – Bas + 1 = 1785048 511523850.

Elles sont toutes identifiables et rien que là, on en a déjà des milliards… de milliards ! Et ce n’est pas fini !

En effet, les étapes suivantes sont les suivantes :

On déplace le bloc [91, 93] jusqu'à ce arrive en position 25, juste à côté de 24. A chaque étape, on calcule la borne basse et la borne haute:
On déplace ensuite, l'élément 24 d'une unité vers la gauche, jusqu'à ce qu'il parvienne en position 1. A chaque fois bien entendu, on répète l'opération en 1

L’écart de position entre le bloc {91,93} et l’élément 24 est constant et est égal à : 91−25=66 positions. Ainsi, lorsque je déplace l’élément 24 vers la gauche jusqu’à ce qu’il se trouve en position 1, il va se déplacer 24-1 = 23 fois .

Donc, dans un premier temps, il y a 23 * 66 = 1518 plages de combinaisons qui contiendront l’élément 24 et jamais 92.

Maintenant éliminons 24 et gardons 92, La procédure est presque identique que pour le numéro 24. Cette fois-ci, c’est 24 que l’on fait disparaitre dans un bloc [23, 25}.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101; dont le rang est 796996192 939409165 248689708 543915974 247409395 684455338 447482450 482094426 116927581

A partir de là, comme précédemment pour 24, on procède en 2 tours: à chaque déplacement du bloc [23,25] vers la gauche jusqu’en position 1, il faudra amener 92 de sa position au bloc [23,25],

On sait que le décalage du bloc [23,25} jusqu’à la position 1 produit :23 – 1 = 22 plages. Ensuite, il faut amener 92 de sa position initiale (92-1=91) jusqu’à la position 25 : 91-25 = 66 fois, A ce stade, on a donc identifié 22*66 = 1452 plages.

Le bloc [23,25] ayant disparu, on doit calculer toutes les plages commençant par les blocs (borne basse) [92,93], [92,94], [92,95]…. [92,301],

Au total, il y aura 1452 + (301-93 +1 ) = 1661 plages + 1 combinaison contenant 92 et jamais 24

Pour finir, cherchons les plages ne contenant ni 24, ni 92. Il n’y a rien de compliqué. On gère en même temps le bloc [23,25] et le bloc [91,93]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102; dont le rang est 796996192 939409165 248689708 543915974 247409395 684455338 447482450 543182752 955743781

Le mode opératoire vous est connu maintenant. On va déplacer le bloc {23,25} (23-1) = 22 fois sur la gauche. Au cours de chaque déplacement, le bloc {91,93} parti de sa position initiale va buter sur le bloc {23,25} : (91-25) = 66 fois.

A chaque tour on calcule H – B + 1 qui est le nombre de combinaisons satisfaisant le critère ni 24 ni 92. A ce stade, on aura 22*66 = 1452 plages ne contenant ni 24, ni 92 et on aura 93 en position 1.

Le dernier élément capable de produire une plage en position 1 est le nombre 300 en borne basse, ce qui donne 301 en borne haute.

Donc on a 1452 + (300 – 93 +1) = 1660 plages + 1 combinaison ne contenant ni 24, ni 92

Conclusion :

Parmi toutes les combinaisons de 100 éléments choisis parmi 400, nous avons montré comment dresser, à partir d’une paire de deux élémentss incompatibles, des plages de combinaisons contenant soit l’un soit l’autre élément de la paire et celles ne contenant ni l’un ni l’autre. Par exemple, pour la paire {24,92} , nous avons compté qu’il existe:

1727 plages de combinaison plus 1 combinaison contenant l’élément 24 mais jamais l’élément 92
1661 plages de combinaison plus 1 combinaison contenant l’élément 92 mais jamais l ’élément 24.
1660 plages de combinaison plus 1 combinaison ne contenant ni 24 ni 92.

Si l’on a X paires d’éléments incompatibles, la procédure devra être répétés X fois, séquentiellement (ou en parallèle si l'ondispose de plusieurs machines) en faisant bien attention aux calculs d’index. Avec une proportion d’ éléments incompatibles d’environ de ½, on aurait alors 200 paires d’incompatibles.

Pour la paire étudié {24, 92}, il y a en tout (1727+1661+1660) = 5048 plages satisfaisant le critère: soit l’un, soit l’autre ou aucun des deux. Comme une plage est bornée par 2 combinaisons, le nombre total de rangs à calculer est égal à 5048*2= 10 096 rangs.

En prenant ce nombre comme moyenne de rangs à produire et sachant que (1) l’algorithme de production des rangs est écrit en langage PHP et (2) est exécuté sur un pc portable doté d’un processeur Intel(R) Core(TM) i3-6006U CPU @ 2.00GHz fonctionnant à 2.00 GHz et (3) doté d’une mémoire RAM de 8 Go, le calcul d’un rang est de l’ordre de 2 millièmes de seconde au plus !!

Ainsi, pour 200 paires d’incompatibles, la production des plages contenant soit l’un, soit l’autre ou aucun des deux, sur une seule machine et d'une manière séquentielle, est de l’ordre de : 10 096 * 0,002*200 = 4039 secondes soit environ 68 minutes.

L’espace nécessaire au stockage
$\frac{400!}{100! (400 - 100)!}$ = 2241854 791554337 561923210 387201698 554845411 177476295 990399942 258896013 007429693 894018935 107174320 est un nombre constitué de 97 chiffres soit 776 octets. En considérant qu’il y a en moyenne 10096 rangs à produire par paire incompatible, pour 200 paires d’incompatibles, il faudra réserver 776*10096*200 = 1 566 899 200 octets soit un peu plus de 1,6 Go sans les données d’identification. On peut donc majorer l’espace de stockage des plages de combinaison à 3Go, ce qui est très largement à portée des disques durs de n’importe quel micro-ordinateur portable ou fixe.

P = NP

Mais d'abord, qu'est-ce que P ? Qu'est-ce que NP ?

La complexité de la transformation d'un problème non déterministe en un problème déterministe

Peut-on alors trouver facilement ce que l'on peut vérifier facilement ?

Application concrète de l'algorithme à un problème typiquement SAT

Méthodologie de résolution

Application au problème d'hébergement exposé par Stephen COOK

Le résultat obtenu est similaire à l'identification d'un atome particulier dans l'univers observable ... et même un peu au-delà !

Livraison des combinaisons «XB1» et «XB2»

Conclusion

Exemple de bornage de plages de combinaisons

Livraison des combinaisons «X_B1» et «X_B2»