Les classes de complexité
Les classes P, NP, NP-complet et NP-difficile, la vérification d'un certificat, la réduction polynomiale, les problèmes de référence (SAT, sac à dos, voyageur de commerce, coloration) et la taille que chaque coût permet de traiter en un temps donné.
- 25 cartes
- 7 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Sur la frise
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Classe P : de quoi s'agit-il ?
Voir la réponse
Ensemble des problèmes de décision qu'un algorithme résout en un temps polynomial en la taille de l'entrée.
Trier, trouver un plus court chemin ou tester la primalité sont dans cette classe. « Polynomial » veut dire borné par n^k pour un k fixe, ce que 2ⁿ ne respecte jamais.
Que veut dire qu'un problème est dans NP ?
- Une solution proposée se vérifie en temps polynomial
- Aucun algorithme polynomial ne peut le résoudre
- Le meilleur algorithme connu pour le résoudre est exponentiel
- Il se résout en temps polynomial seulement sur une machine quantique
Voir la réponse
Une solution proposée se vérifie en temps polynomial
NP vient de « non-déterministe polynomial », pas de « non polynomial ». Tous les problèmes de P sont aussi dans NP : résoudre vite permet de vérifier vite.
Une solution proposée s'appelle un … ; un problème est dans NP si le certificat se vérifie en temps ….
Voir la réponse
Une solution proposée s'appelle un certificat ; un problème est dans NP si le certificat se vérifie en temps polynomial.
Pour SAT, le certificat est une affectation des variables : il suffit de l'évaluer clause par clause, un temps linéaire en la taille de la formule.
Classe NP : de quoi s'agit-il ?
Voir la réponse
Ensemble des problèmes de décision dont une solution proposée, appelée certificat, se vérifie en temps polynomial.
Le critère porte sur la vérification, pas sur la recherche : on ne sait pas si trouver la solution peut toujours se faire aussi vite. C'est la question P = NP.