Dans la deuxième partie , nous avons calculé la complexité de la multiplication scolaire à N chiffres : il s'agit d'un calcul à temps quadratique, nous avions vu que l'addition scolaire est un calcul à temps linéaire dans la première partie
Nous avions conclut que ces deux opérations appartiennent à l'ensemble P, qui représente l'ensemble des calculs déterministes à temps polynomial.
Dans la conjecture P = NP, l'ensemble NP représente les calculs non déterministes à temps polynomial. Mais avant de revenir sur cet ensemble plus en détail, il nous faut voir une dernière notion.
Avant, je dois préciser que certains passages peuvent contenir des erreurs pour deux raisons : d'une part, je ne suis pas un spécialiste de la théorie de la complexité et encore moins du problème P = NP. D'autre part, je présenterai à certains endroits mon point de vue, qui là encore peut contenir des erreurs ou même sembler simpliste aux spécialistes, vous voilà prévenus...
Les calculs à temps exponentiel
Imaginons que l'on souhaite connaître le nombre d'ancêtres A que nous avons, pour une génération N, par exemple :
A(1) = 2 (parents)
A(2) = 4 (grands parents)
A(3) = 8 (arrière grands parents)
...
A(N) = 2^N
Pour calculer A(N), il nous faut multiplier le résultat précédent A(N-1) par deux. En prenant comme opération unitaire la multiplication, on a donc un calcul à temps exponentiel, c'est à dire du type :
T(calcul exponentiel) = K^N
Où K est un nombre fixé (2 dans le cas du calcul des ancêtres) et N le nombre de données (dans notre exemple, le nombre de générations)
Un point fréquent dans les calculs à temps exponentiels est qu'ils sont récursifs : pour calculer A(N), on doit calculer A(N-1). Le résultat final n'est possible qu'en faisant tous les calculs
Mon point de vue : On peut se représenter le calcul à temps polynomial ou exponentiel comme une série de calculs à effectuer dans l'ordre : les calculs sont "branchés" en série, un peu comme des composants d'un circuit électrique. Tous les "circuits sont nécéssaires pour alimenter" le résultat. Les problèmes P ou E (voir plus bas) sont des "calculs en ET".
Nous pouvons maintenant définir l'ensemble E, comme étant l'ensemble des calculs à temps exponentiel. Mais quel rapport avec P = NP ? En quoi cela peut-il nous aider à définir l'ensemble NP ?
Calculs non déterministes à temps polynomial
Que signifie un calcul "non déterministe" ? En gros, que l'algorithme doit effectuer un certain nombre de calculs indépendants les uns des autres et qu'en fonction du "choix" qu'il fera, il pourra mettre moins de temps que nécéssaire, s'il avait dû tous les calculer, ou s'il les avait calculé dans un "ordre déterministe".
Pour cette raison, on dit souvent que les problèmes de la classe NP sont des problèmes de "décision".
On observe plusieurs propriétés importantes des problèmes de la classe NP :
- On peut calculer un problème NP avec un algorithme à temps exponentiel
- On peut vérifier le calcul d'un problème NP avec un algorithme à temps polynomial
On voit qu'en terme d'efficacité, les problèmes NP semblent se situer "entre" les problèmes P et E.
Autre point important : un problème P fait également partie de la classe NP. En termes ensembliste, on dira que l'ensemble P est inclus dans l'ensemble NP.
En mathématique, pour que deux ensembles (P et NP) soient égaux, il faut (et il suffit) qu'ils soient inclus l'un dans l'autre. Nous savons déjà que P est inclus dans NP. Toute la question de l'hypothèse P = NP est en fait de savoir si la réciproque est vraie : En fait la question n'est pas "P est-il égal à NP ?", mais plus précisément "NP est-il inclus dans P ?", autrement dit :
Pour chaque problème NP, existe-il un algorithme déterministe à temps polynomial capable de le résoudre ?
Généralement, les problèmes mathématiques commençant par "Pour chaque...existe t'il..." sont les plus difficiles à résoudre , car il faut démontrer l'existence d'un tel algorithme pour chaque problème, mais comment peut-on étudier en même temps TOUS les problèmes de type NP ? (Une blague de mathématicien serait de dire qu'on se trouve en face d'un problème à temps exponentiel...)
En fait, dans les années 60, un mathématicien américain du nom de Stephen Cook a découvert qu'on pouvait étudier tous les problèmes d'une classe, en étudiant uniquement "les plus difficiles" de cette classe : En résumé, "qui peut le plus, peut le moins". On appelle ces problèmes des problèmes complets.
Un problème NP-Complet : le problème du voyageur
Imaginons qu'un touriste veuille visiter N villes. Il souhaite effectuer le trajet le plus court possible, ou plus précisément, plus court qu'une certaine distance autorisée, qu'on appelera D, tout en passant par toutes les villes.
Pour résoudre ce calcul il faudrait à priori calculer toutes les combinaisons possibles de trajets, soit (N-1)! et sélectionner uniquement celles inférieures à D, par exemple :
Pour deux villes (N=2), il y a 1 seul trajet possible (T=1), donc une seule distance à calculer.
N = 3, T = 2
N = 4, T = 6
N = 5, T = 24
...
N = k, T = (k-1)! = (k-1) * (k-2) * ... * 1
On retrouve un peu le même schéma que pour le calcul des ancêtres (à temps exponentiel) : une série de multiplications, on peut donc à priori classer cet algorithme dans l'ensemble E.
Cependant, on peut vérifier si notre solution est correcte en beaucoup moins de temps : en faisant la somme des distances des trajets parcourus, on obtient une distance qui doit nécéssairement être inférieure à D. L'algorithme de vérification appartient à la classe P, car le temps de calcul est proportionnel au nombre de villes.
Ces deux éléments (calcul dans E et vérification dans P) suffisent à classer notre problème dans la catégorie NP.
En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. On peut reformuler la conjecture P = NP comme cela :
Si on parvient à trouver un algorithme déterministe à temps polynomial pour résoudre le problème du voyageur, alors on pourra le faire pour n'importe quel problème NP. La classe NP sera alors réduite à la classe P.
Le problème, c'est que personne n'a encore trouvé d'algorithme déterministe à temps polynomial pour aucun problème NP-Complet, donc pour l'instant, force est de constater que P n'est pas égal à NP !
Mon point de vue : P n'est pas égal à NP
Comme je l'ai dit dans la première partie de cet article, je ne suis pas un spécialiste, pourtant, en lisant divers articles sur le problème P = NP, dont l'excellent livre "les énigmes mathématiques du 3ème millénaire", je me suis mis à rêver d'une légitimité pour donner ma conception de ce problème... Voici mon idée, peut-être naïve ou stupide, mais c'est une idée...
Les problèmes NP consistent à effectuer plusieurs calculs, qui sont à priori pas tous nécéssaires, pour les résoudre : Dans le problème du voyageur, "si on a de la chance", on peut tomber sur le plus court trajet du premier coup, pas besoin de tous les calculer.
On peut se représenter les problèmes NP comme des calculs "en parallèle" (comme dans un circuit électrique), nous n'avons pas besoin "d'alimenter tous les circuits" pour arriver au résultat. Les problème NP sont des "calculs en OU".
J'ai dit plus haut que les problèmes P ou E sont des "calculs en ET". D'où la nécéssité d'effectuer TOUS les calculs pour arriver au résultat.
Les mathématiciens, car il existe de nombreuses méthodes (appelées heuristiques) pour trouver les meilleurs chemins, ont conjecturé qu'un problème NP ("calcul en OU") n'est pas aussi complexe qu'un problème E ("calcul en ET"). ET que donc, on pouvait réduire les problèmes NP à des problèmes P ("calculs en ET") beaucoup plus simples que le problème E ("calcul en ET") équivalent.
Mon idée est que pour un algorithme donné, il existe un seul "calcul en ET" et que celui-ci est nécéssairement le problème E d'origine. Je dirais donc que NP n'est pas inclus dans P mais qu'au contraire, NP est inclus dans E.
Je pense que le meilleur moyen de résoudre un problème NP est donc d'utiliser ces heuristiques ou des algorithmes non déterministes comme par exemple les algorithmes génétiques.
Car il est vrai qu'un problème NP se distingue d'un problème E, par la possibilité de "sauter" des étapes du calcul, mais je suis convaincu qu'il n'existe pas de "formule magique" pour effectuer ce choix, on peut simplement éviter de faire de "mauvais choix" (heuristiques), ou expérimenter des échantillons prometteurs de choix (algo génétique).
J'ai bien conscience qu'il s'agit d'un avis tranché, sans aucun vrai argument scientifique ou mathématique. J'essayerai d'étayer cette idée plus tard avec, si je peux, des arguments plus rigoureux ou à défaut, par d'autres images peut-être plus convaincantes.
Une dernière précision sur P = NP : on peut se poser la question de savoir si cette conjecture est démontrable (ou réfutable). Autrement dit, il y a trois réponses possibles à la question P = NP ?
1- Vrai
2- Faux
3- Indémontrable
J'ai dis que je pensais que la réponse était Faux, mais je dois avouer que la troisième solution est tentante : Cela pourrait signifier soit une limite dans les outils mathématiques à notre portée (3A), soit que la question n'a pas de sens dans l'absolu (3B).
En résumé, je pencherais pour la solution 2 ou - dans une moindre mesure - la solution 3B.
Et vous, qu'en pensez-vous ? Quelle solution vous semble la plus plausible ?
PS : Si j'ai commis des erreurs dans cet article, je vous prie de m'en excuser, je n'aime pas trop me documenter pour écrire, mon but n'était pas de faire une "leçon" sur la théorie de la complexité. N'hésitez pas à apporter des corrections si nécéssaire.
Inscription à :
Publier les commentaires (Atom)
4 commentaires:
Salut je m'appelle Rafik et la théorie de la complexité m'intéresse un peu. D'abord je voudrais te féliciter pour la présentation de la complexité, c'est vachement bien fait même si j'ai quelques remarques à faire mais pas pour cette fois-ci! Sinon, moi je ne conforte aucune conjecture concernant la comparaison entre NP et P car les problèmes d'optimisation combinatoire sont si simples à formuler que je ne vois pas quelles informations utiles pour trancher cette question pourrait-on extirper de plus de leurs modèles du coup c'est difficile d'emettre un avis. Je ne crois pas que philosopher sur cette question nous menerait à grand chose. Je crois que c'est les efforts de calculs sur des problèmes NP-complets particuliers qui nous éclaireront un peu (enfin je l'espère). Concernant l'"indémontrabilité", elle est possible mais je ne crois pas qu'on puisse la prouver car pour les mêmes raisons citées plus haut, je dirais que si l'on peut prouver l'"indémontrabilité" c'est que l'on peut prouver la démontrabilité, c'est-à-dire je ne vois pas quelqu'un pouvoir le faire sans passer par la réponse à la question de la comparaison entre NP et P (il est 6h21mn et j'ai pas fermé les yeux de la nuit mais j'essaierai de te réécrire pour argumenter)!!!!!! Voilà, je te laisse mon MSN si tu veux discuter en live, en tout cas ça m'intéresserait moi: rafik_jordan@hotmail.com. STP envoie-moi un e-mail avant pour savoir que c'est toi que je vais ajouté (je me méfie des virus!). Allez a bientôt.
Bonjour!
Félicitation pour cet article, je suis très content de voir que des personnes non spécialistes puissent s'intéresser à la NP-Complétude...
Je trouve que la manière dont tu as présenté les choses est très didactique.
Cependant je voudrais préciser une chose sur la théorie de la complexité... Bien que subtile voire ardue elle demeure en fait plus simple que dans tes exemples! Tu dénombres rigoureusement le nombre d'opérations, là ou en réalité nous comptons à la louche! Les temps des algorithmes sont toujours des ordres de grandeurs... Pourquoi? Pour des raisons analogues à tes arguments au sujets des temps d'exécutions : on ne peut savoir combien d' opérations prendra une primitive dans tel ou tel langage de programmation par rapport à un autre, d'une part, et surtout (faut bien l'avouer) car on s'en fout d'être précis (contrairement aux statistiques par exemple) car le seul but d'un tel calcul est de garantir un temps d'exécution au pire des cas...
Autrement dit un algorithme quadratique ou cubique sera un algorithme linéaire dans tous les cas... En fait devant un temps exprimé comme un polynôme en fonction de la taille de l'entrée, on ne conserve que le terme de plus au degré!
Pour simplifier seule trois grande catégories sont intéressantes : temps logarithmique, temps linéaire, temps exponentiel...
Après pour être tout à fait franc, c'est le boulot d'un bon développeur que de remarquer que les négligences théoriques ont de grosses conséquences dans la pratique et qu'il se doit de soigner tous les détails :D
Je tiens à faire remarquer (dans une démarche constructive et que j'espère enrichissante :) ) qu'il est faux de lier algorithmes non-déterministes, problèmes NP et problème de décision de cette manière. Un problème est dit de décision dès lors que sa formulation est une question en gros de la forme « Existe t-il... ? » et auquel on doit décider soit « oui » soit « non »...
Ensuite, un algorithme n'est pas déterministe dès lors qu'un aléas intervient, grosso modo si en l'exécutant plusieurs fois sur une même entrée il peut produire des résultats différents, contrairement à un algorithme déterministe qui donnera invariablement la même sortie...
Bref les problèmes NP sont des problèmes qui ont des solutions en temps polynomial MAIS sur des machines non déterministes ou avec des algorithmes non déterministes... Tout la question P=NP est donc de savoir s'il en est de même sur des machines déterministes et avec des algorithmes déterministes (dites de Turing, ie nos ordinateurs!)
« En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. »
Encore une petite confusion terminologique (c'est une subtilité ici je l'accorde :D ) on parle de problème NP-Complet si le problème est donné sous forme d'un problème de décision (comme je viens de le définir) est de problème NP-Difficile si le problème est donné sous forme d'un problème d'optimisation.
Les deux versions sont équivalentes en difficulté (je pourrais l'expliquer si tu veux... ) mais la forme est différente (pour un problème d'optimisation on cherche le plus grand ou le plus petit objet – selon le sens de la difficulté! - ayant telle liste de propriétés et non pas de savoir s'il existe ou non un objet de taille k...)
A ta disposition pour toute conversation sur le sujet,
Pierre.
debianholic@gmail.com
Salut Pierre. C'est bien tes précisions sur la complexité, c'est plus clair dans ma tête même si elles ne m'étaient pas spécialement destinées!
Néanmoins je voulais connaitre si possible ton avis sur la comparaison entre P et NP.
A bientôt.
P.-S: Mon adresse hotmail: rafik_jordan@hotmail.com.
Bonjour Pierre,
Je te remercie de ces précisions très intéressantes.
En fait, je ne savais pas que le terme "NP-Difficile" avait un sens bien précis et je te remercie de me l'avoir appris. ;)
Et effectivement, il m'a semblé que les problème NP étaient TOUS des problèmes de décision, alors que si je comprends bien, cela ne concerne que les problème NP-Complets.
En fait, je pensais que la "décision" représentait les aléas (mon point de vue était que le dé, lorsqu'il tombe sur six, a pris une décision), mais je dois reconnaître que le fait de définir un problème de décision par la possibilité de l'exprimer sous la forme "Existe-t'il..." est bien plus rigoureuse et plus large que le sujet des problèmes NP.
"Bref les problèmes NP sont des problèmes qui ont des solutions en temps polynomial MAIS sur des machines non déterministes... "
J'avais une question concernant l'aspect "non déterministe" : pensez-vous que l'on puisse réellement construire un algorithme ou une machine non déterministe te si oui comment ?
Mon point de vue serait de dire que ce qui est déterministe est déterminé et que donc, on ne peut "déterminer" un algorithme non déterministe...
Est-ce qu'un générateur de nombres aléatoire peut être une bonne "approximation" pour créer un algorithme non déterministe ?
En informatique, la fonction qui produit un résultat différent à chaque appel le fait parce qu'il y a en réalité d'autres paramètres (par exemple une amorce ou "seed"), mais si l'on passait l'amorce en entrée (car c'est en fait un paramètre d'entrée), la fonction serait déterministe, car tous les paramètres d'entrée seraient déterminés.
En bref : A quoi ressemblerait une machine ou un algorithme non déterministe ?
Je vous remercie de votre intervention. A très bientôt.
Mathieu.
Enregistrer un commentaire