Complexité : Instance
Cet article traite des instances dans le cadre de la théorie de la complexité.
Définition : Instance
Une instance (la donnée) est un objet mathématique, sur lequel nous posons une question dont on attend une réponse (la sortie). [1]
Un algorithme est une méthode de résolution générale à ce problème. Cet algorithme prend en entrée l’instance du problème et retourne la solution en sortie. [1]
En résumé : L’instance d’un problème est la donnée d’entrée de ce problème. Elle sera l’entrée de l’algorithme résolvant ce problème. [2]
Instances positives et instances négatives
Une instance positive d’un problème de décision est une instance (une donnée) pour laquelle ce problème a pour sortie “Vrai”.
A contrario, une instance négative impliquera une sortie “Faux”.
Pour rappel, un problème de décision est un problème pour lequel la sortie est soit vrai (“Oui”), soit fausse (“Non”).
Exemples
Pour le problème PRIMALITY (= est-ce que un entier $n$ est un nombre premier ?) :
- L’ensemble de ses instances est $\mathbb{Z}$.
- L’ensemble de ses instances positives est $\mathbb{P}$.
- L’ensemble de ses instances négatives est $\mathbb{Z} - \mathbb{P}$.
$\mathbb{P}$ est l’ensemble des nombres premiers.