En
informatique théorique, et notamment en
théorie de la complexité un problème
complet pour une classe de complexité, est un
problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème.