Quelques précisions sur les problèmes P, NP et NP-complet:
P signifie Polynomial: il existe un algorithme qui resout le problême en un temps polynomial dans le pire cas.
NP ne signifie pas non polynomial mais Non-deterministic Polynomial. Cela signifie qu'il est possible en temps polynomial de tester si un candidat X est ou n'est pas solution du problème.
Un problème P est un problème NP tout comme un carré est un rectangle.
En géneral, on parle de problème NP-complet pour désigner les problèmes de complexité exponentielle , car il existe un théorème (le théorème de Cook) qui indique que certains problemes NP (dits NP-complet) sont équivalents, et qui si on peut en résoudre un de manière polynomiale, alors on peut résoudre les autres aussi.
[^] # Re: Un nouvel algo de compression ?
Posté par Gaël Le Mignot . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à 0.
P signifie Polynomial: il existe un algorithme qui resout le problême en un temps polynomial dans le pire cas.
NP ne signifie pas non polynomial mais Non-deterministic Polynomial. Cela signifie qu'il est possible en temps polynomial de tester si un candidat X est ou n'est pas solution du problème.
Un problème P est un problème NP tout comme un carré est un rectangle.
En géneral, on parle de problème NP-complet pour désigner les problèmes de complexité exponentielle , car il existe un théorème (le théorème de Cook) qui indique que certains problemes NP (dits NP-complet) sont équivalents, et qui si on peut en résoudre un de manière polynomiale, alors on peut résoudre les autres aussi.
Pour plus d'informations, voir le rapport que l'un des mes camarades a fait:
http://www.epita.fr:8000/~barada_n(...)