Je pense que si. Au premier livre d'algorithmique que tu aurais ouvert.
Et bien tu me pretes des qualites que je n'ai pas, car sans mes bases de prepa j'aurais eu un peu de difficultes, et sans etre force a comprendre ce que sont vraiment les classes de complexite j'aurais abandonner rapidement.
par contre je sais pas comment tu fait pour les "reconaitre" dans le cas général, j'avais l'impression que ça faisait l'objet de preuves au cas par cas
Un probleme est NP-complet s'il peut se reduire a un autre probleme NP-complet. Quand on connait les principaux problemes NP-complets (SAT, voyageur de commerce, coloration de graphe...) on arrive a voir que les problemes qu'on essaye de resoudre sont equivalents a l'un de ceux-la.
C'est comme ça que ça c'est passé pour moi et je pense pas être le seul. La preuve, c'est qu'à mon avis une bonne partie des linuxfriens qui lisent ce post sans comprendre certains mots vont chercher sur la wikipedia.
Oui. Et sur wikipedia, ils vont trouver ca:
Classe NP : c'est la classe des problèmes de décision pour lesquels la réponse oui peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l'instance.
Bon, donne ca a un lyceen de base qui se prend pour Blake Ross ("pas besoin de faire des etudes pour etre informaticien !") et regarde la tete qu'il fait :).
[^] # Re: Enfin bon
Posté par Erwan . En réponse au journal Les informaticiens précoces. Évalué à 2.
Et bien tu me pretes des qualites que je n'ai pas, car sans mes bases de prepa j'aurais eu un peu de difficultes, et sans etre force a comprendre ce que sont vraiment les classes de complexite j'aurais abandonner rapidement.
par contre je sais pas comment tu fait pour les "reconaitre" dans le cas général, j'avais l'impression que ça faisait l'objet de preuves au cas par cas
Un probleme est NP-complet s'il peut se reduire a un autre probleme NP-complet. Quand on connait les principaux problemes NP-complets (SAT, voyageur de commerce, coloration de graphe...) on arrive a voir que les problemes qu'on essaye de resoudre sont equivalents a l'un de ceux-la.
C'est comme ça que ça c'est passé pour moi et je pense pas être le seul. La preuve, c'est qu'à mon avis une bonne partie des linuxfriens qui lisent ce post sans comprendre certains mots vont chercher sur la wikipedia.
Oui. Et sur wikipedia, ils vont trouver ca:
Classe NP : c'est la classe des problèmes de décision pour lesquels la réponse oui peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l'instance.
Bon, donne ca a un lyceen de base qui se prend pour Blake Ross ("pas besoin de faire des etudes pour etre informaticien !") et regarde la tete qu'il fait :).