Complexité : Instance
Cet article traite des instances dans le cadre de la théorie de la complexité.
This article has been written by Robin Pourtaud ([email protected]) and published on September 7, 2021.
The content of this article is licensed under CC BY
NC 4.0 : You can freely share and adapt the content for non-commercial purposes as long as you give
appropriate credit and provide a link to the license. In my case, the link to the original article is enough.
Confidentiality if relevant: https://devmath.fr/page/confidentialite/
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.