Vocabulaire

La complexité s’intéresse à :

Un problème de décision A, une question portant sur un ensemble de données dont la réponse est OUI ou NON. Ne pas confondre problème et algorithme.
Un problème calculatoire, dont la réponse n’est pas nécessairement une réponse binaire (oui/non).
Un problème d’optimisation.
Une instance du problème A, la question posée sur une donnée particulière de A.

Exemple:
Donnée : Un nombre entier positif n en base 2
Question : n est-il pair ?