classe de complexité NP

classe NP
problème NP

INFORMATIQUE

La classe de complexité NP (non déterministe polynomial) est la classe de complexité des problèmes de décision qui peuvent être résolus par un algorithme
polynomial non déterministe. C’est une extension de la classe P.

On dit qu’un problème est dans NP s’il existe un algorithme pour vérifier qu’une solution donnée convient en un temps polynomial.