Pour info, la classe NP regroupe l'ensemble des problèmes dont une entrée donnée peut être validée ou invalidée en temps polynomial.
par exemple, pour SAT (satisfiabilité d'une formule logique), si on se donne un ensemble de valeur booléennes, on peut savoir si la réponse est 0 (false) ou 1 (true) en temps polynomial. Par contre, si on se retrouve avec 0 (false), il est difficile de savoir si la formule est satisfiable ou non.
Là, tu ne pourra pas dire que je n'ai pas été précis, mais va écrire ça dans des parenthèses !!! :-)
J'ai l'impression que les gens sont vachement sensibles ici ! 8-)
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 4.
J'ai dit ça pour aller plus vite.
Pour info, la classe NP regroupe l'ensemble des problèmes dont une entrée donnée peut être validée ou invalidée en temps polynomial.
par exemple, pour SAT (satisfiabilité d'une formule logique), si on se donne un ensemble de valeur booléennes, on peut savoir si la réponse est 0 (false) ou 1 (true) en temps polynomial. Par contre, si on se retrouve avec 0 (false), il est difficile de savoir si la formule est satisfiable ou non.
Là, tu ne pourra pas dire que je n'ai pas été précis, mais va écrire ça dans des parenthèses !!! :-)
J'ai l'impression que les gens sont vachement sensibles ici ! 8-)