NP (complexité)

Domaine

Algorithme
Théorie de la complexité
Coulombe

Définition

En théorie de la complexité, la classe de complexité NP (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long.

Français

NP (complexité)

Anglais

NP (complexity)

source :