par exemple : Ces problèmes, n'appartenant ni à la classe P, ni à la classe E, sont dits de classe NP, non déterministe polynomiaux.
C'est vrai mais le Hic c'est que l'on ne peu pas toujours démontrer à quelle classe appartient un problème (demandant un algorithme forcément exponentiel ou non), et c'est ca qui est intéressant.
En effet certain problèmes de E sont des NP, mais on ne le sait pas, et certain NP sont polynomiaux - classe P - , et c'est pas sûr non plus.
Les limites entre les problèmes sont floues (du point de vue humain), et théoriquement nettes - d'où le racourci de la page citée.
# Autre piste ...
Posté par Anonyme . En réponse au message Complexité d'algorithmes. Évalué à 3.
Il s'agit de classer les problèmes selon la complexité des algorithmes pour les résoudre.
http://wwwsi.supelec.fr/yb/projets/algogen/NP-Complet.htm(...)
Cette page est un peu simpliste, mais explique bien les concepts.
par exemple :
Ces problèmes, n'appartenant ni à la classe P, ni à la classe E, sont dits de classe NP, non déterministe polynomiaux.
C'est vrai mais le Hic c'est que l'on ne peu pas toujours démontrer à quelle classe appartient un problème (demandant un algorithme forcément exponentiel ou non), et c'est ca qui est intéressant.
En effet certain problèmes de E sont des NP, mais on ne le sait pas, et certain NP sont polynomiaux - classe P - , et c'est pas sûr non plus.
Les limites entre les problèmes sont floues (du point de vue humain), et théoriquement nettes - d'où le racourci de la page citée.