NP-complétude faible

Résumé

En informatique théorique, plus précisément en théorie de la complexité, un problème est faiblement NP-complet s'il est NP-complet mais qu'il admet un algorithme en temps polynomial si on encode les entiers contenus dans les entrées en unaire.

Source officielle

https://fr.wikipedia.org/wiki/NP-complétude_faible

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.