Complexité computationnelle

Concepts en informatique

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Classes de complexité

Classes de complexité

Une animation montrant tout l’espace de complexité des problèmes

Une image montrant l’espace de problèmes P

Classe de complexité -->	P (temps polynomial)
Signification	Se résout vite et efficacement
Exemple	Trier une liste
Analogie	« Classer des documents par ordre alphabétique »
Point clé	« Faciles » au sens computationnel

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Une image montrant les espaces de problèmes P et NP

Classe de complexité -->	NP (temps polynomial non déterministe)
Signification	Solution vérifiable, difficile d’en trouver une nouvelle
Exemple	Vérifier qu’un Sudoku est correct
Analogie	« Trouver un document précis avec des infos manquantes »
Point clé	Vérifier est « facile », trouver une nouvelle solution est difficile

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Une image montrant les espaces de problèmes P, NP et NP-Complet

Classe de complexité -->	NP-Complet
Signification	Les plus difficiles de NP. Spéciaux car résolvent tous les problèmes NP
Exemple	Problème du voyageur de commerce
Analogie	« Casse-tête complexe : facile à vérifier, difficile à résoudre »
Point clé	Aucun algorithme efficace connu. S’il en existe un, il résout tout NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Une image montrant les espaces P, NP, NP-Complet et NP-Difficile

Classe de complexité -->	NP-Difficile
Signification	Aussi difficile que NP-Complet ou plus
Exemple	Ordonnancement optimal avec fortes dépendances, non vérifiable
Analogie	« Planifier une réunion optimale avec beaucoup de contraintes, non vérifiable rapidement »
Point clé	Peut être irréaliste à résoudre en pratique

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un schéma posant la question classique : P=NP ?

Concepts en informatique