Puisque j'en suis à expliquer des trucs, continuons.
Si on a deux problème A et un B et qu'on peut transformer A pour en faire un
problème B rapidement -- par exemple en temps polynomial, alors le problème
A est plus cimple que le problème B. En effet, si on sait résoudre B, alors on sait
résoudre A: on prend A, on transforme en B, on résoud le problème B
correspondant et on obtient la soluce. Pour ceux qui suivent, je donne un exemple
après.
De cette façon, on peut définir des hiérarchies de problèmes.
Si on se donne des réductions polynomiales et que NP!=P, il existe des problèmes
NP qui sont plus compliqué que n'importe quel problème P. Dans ce cas, la
relation d'ordre obtenue n'est pas ridicule. On peut chercher les problèmes NP
les plus difficiles. Or Steve Cook à montré en 71 que tous les problèmes NP étaient plus simple que SAT. On a donc une classe de problèmes NP qui sont
les plus difficiles: les problèmes NP-complets. Et si on montre qu'un seul de ses
problèmes est dans P, ben alors P=NP.
Frédéric
P.S. pour les plus courageux.
SAT: une formule du type (a ou b ou non c ou d...) et (non a ou c...) et ...
est-elle satisfiable?
3-SAT: SAT dans lequel les (a ou b ou non ) comportent exactement 2 ou.
Exemple de réduction: SAT est plus simple que 3-SAT.
Si on a une clause (a ou b ou c ou d), on ajoute une variable e et on écrit:
( (a ou b)<=> e) et (e ou c ou d).
Si on arrive à écrire (a ou b)<=>e sous la bonne forme, on a gagné.
(a ou b)<=> e s'écrit (a ou b)=>e et e=>(a ou b).
Or u=>v s'écrit (non u) ou v:
e=>(a ou b) s'écrit donc ((non e) ou a ou b) (chouette, on y arrive).
et
(a ou b)=>e s'écrit:
- (non (a ou b)) ou e;
- donc ( (non a) et (non b)) ou e;
- donc ((non a) ou e) et ((non b) ou e).
La formule (a ou b ou c ou d) s'écrit donc
(e ou c ou d) et ((non e) ou a ou b) et ((non a) ou e) et ((non b) ou e) qui est
bien de la forme voulue.
De plus on montre que la taille de la formule obtenue est polynomiale en la
taille de la formule initiale.
On a codé une formule SAT dans une formule 3-SAT et la première formule est
satisfiable si et seulement si la seconde l'est.
SAT est plus simple que 3-SAT donc 3-SAT est NP-complet.
[^] # Re: Algorithme génétique ?
Posté par fmaz fmaz . En réponse à la dépêche Améliorer les performances du noyau avec un algorithme génétique. Évalué à 4.
Si on a deux problème A et un B et qu'on peut transformer A pour en faire un
problème B rapidement -- par exemple en temps polynomial, alors le problème
A est plus cimple que le problème B. En effet, si on sait résoudre B, alors on sait
résoudre A: on prend A, on transforme en B, on résoud le problème B
correspondant et on obtient la soluce. Pour ceux qui suivent, je donne un exemple
après.
De cette façon, on peut définir des hiérarchies de problèmes.
Si on se donne des réductions polynomiales et que NP!=P, il existe des problèmes
NP qui sont plus compliqué que n'importe quel problème P. Dans ce cas, la
relation d'ordre obtenue n'est pas ridicule. On peut chercher les problèmes NP
les plus difficiles. Or Steve Cook à montré en 71 que tous les problèmes NP étaient plus simple que SAT. On a donc une classe de problèmes NP qui sont
les plus difficiles: les problèmes NP-complets. Et si on montre qu'un seul de ses
problèmes est dans P, ben alors P=NP.
Frédéric
P.S. pour les plus courageux.
SAT: une formule du type (a ou b ou non c ou d...) et (non a ou c...) et ...
est-elle satisfiable?
3-SAT: SAT dans lequel les (a ou b ou non ) comportent exactement 2 ou.
Exemple de réduction: SAT est plus simple que 3-SAT.
Si on a une clause (a ou b ou c ou d), on ajoute une variable e et on écrit:
( (a ou b)<=> e) et (e ou c ou d).
Si on arrive à écrire (a ou b)<=>e sous la bonne forme, on a gagné.
(a ou b)<=> e s'écrit (a ou b)=>e et e=>(a ou b).
Or u=>v s'écrit (non u) ou v:
e=>(a ou b) s'écrit donc ((non e) ou a ou b) (chouette, on y arrive).
et
(a ou b)=>e s'écrit:
- (non (a ou b)) ou e;
- donc ( (non a) et (non b)) ou e;
- donc ((non a) ou e) et ((non b) ou e).
La formule (a ou b ou c ou d) s'écrit donc
(e ou c ou d) et ((non e) ou a ou b) et ((non a) ou e) et ((non b) ou e) qui est
bien de la forme voulue.
De plus on montre que la taille de la formule obtenue est polynomiale en la
taille de la formule initiale.
On a codé une formule SAT dans une formule 3-SAT et la première formule est
satisfiable si et seulement si la seconde l'est.
SAT est plus simple que 3-SAT donc 3-SAT est NP-complet.