Forum de mathématiques - Bibm@th.net

wiisem

Membre

Inscription : 12-01-2006

Messages : 1

complexité algorithmique

Bonjour
Je voudrais SVP, une explication sur les classes des problèmes P, NP, NP-complet et NP-difficile.
Qu'est ce qu'on veut dire exactement par un problème se réduit polynomialement à un autre
Une formulation PLNE, SAT et CSP pour les problèmes suivants:
problème du voyageur de commerce, problème du sac à dos, problème de la clique et des n reines
Merci(SVP c urgent)

tµtµ

Invité

Re : complexité algorithmique

Salut,

Impossible de résumer en 2 lignes une telle théorie, en plus c'est bien expliqué là :

http://fr.wikipedia.org/wiki/Th%C3%A9or … exit%C3%A9