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. Wikipedia