NP-complétude faible
Cet article est orphelin. Moins de trois articles lui sont liés ().
Vous pouvez aider en ajoutant des liens vers [[NP-complétude faible]] dans les articles relatifs au sujet.
Cet article ne cite aucune source et peut contenir des informations erronées (signalé en février 2023).
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
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.
