Test de propriété

L'algorithme a les propriétés suivantes :

• accepte ${\displaystyle x}$ avec une probabilité ${\displaystyle p\geq 2/3}$ si ${\displaystyle x\in {\mathcal {P}}}$;
• rejette ${\displaystyle x}$ avec une probabilité ${\displaystyle p^{\prime }\geq 2/3}$ si ${\displaystyle d(x,{\mathcal {P}})\geq \epsilon }$;
• peut renvoyer n'importe quel résultat avec une probabilité quelconque si ${\displaystyle 0<d(x,{\mathcal {P}})<\epsilon }$.

Comme pour un algorithme de Monte-Carlo classique, si ${\displaystyle p}$ ou ${\displaystyle p^{\prime }}$ vaut 1, l'algorithme est dit à erreur unilatérale. Sinon, il est dit à erreur bilatérale[3].

Il existe plusieurs modèles de test. En particulier, on peut définir plusieurs distances et type de requêtes selon la densité des graphes en entrées : des graphes denses, des graphes creux ou des graphes généraux.

La distance choisie sur l'ensemble E est particulièrement importante. Les résultats obtenus avec une distance donnée ne sont pas valables si on la change. Par exemple, dans le cas des graphes, on peut obtenir des résultats complètement différents selon que l'on se limite aux graphes denses, aux graphes peu denses, ou que l'on étudie les graphes en général[4].

La distance pour les graphes denses entre deux graphes est souvent le nombre d'arêtes à changer divisé par ${\displaystyle n^{2}}$. La distance pour les graphes creux ou généraux entre deux graphes est souvent le nombre d'arêtes à changer divisé par ${\displaystyle max(n,m)}$.

Selon les versions, l'algorithme choisit les requêtes, ou bien elles lui sont présentées selon une certaine distribution.

Pour les graphes denses, les requêtes sont de la forme : "est-ce que (u,v) est une arête du graphe ?", alors que pour les graphes creux, elles sont du type "quel est le degré du nœud u ?" ou "quel est le i-ème voisin du nœud u ?".

Une autre différence importante entre les modèles est que certains modèles sont non-adaptatifs, c'est-à-dire que toutes les requêtes sont choisies à l'avance, alors que certains sont adaptatifs, c'est-à-dire que la réponse à une requête peut être utilisée pour les requêtes suivantes.

Nous choisissons comme ensemble ${\displaystyle {\mathcal {P}}}$ l'ensemble des graphes colorables avec 3 couleurs. Le problème de la 3-coloration est connu NP-complet, donc aucun algorithme à complexité polynomiale n'est connu à ce jour pour le résoudre. Cependant, Alon et Krielevich ont proposé un testeur de propriété fonctionnant en temps constant pour le résoudre[5].

L'algorithme en lui-même est un exemple très générique de testeur de propriété. Il reçoit en entrée un graphe ${\displaystyle G}$ et un paramètre de distance ${\displaystyle \epsilon }$. De plus, la distance choisie est telle que si le graphe ${\displaystyle G}$ possède ${\displaystyle n}$ sommets, il sera à une distance ${\displaystyle \epsilon }$ de ${\displaystyle {\mathcal {P}}}$ s'il faut lui enlever ${\displaystyle \epsilon n^{2}}$ arêtes pour qu'il soit dans ${\displaystyle {\mathcal {P}}}$.

L'algorithme sélectionne aléatoirement ${\displaystyle 108\ln(k)/\epsilon ^{2}}$ sommets du graphe ${\displaystyle G}$, et reconstitue le sous-graphe induit par ces sommets. Il vérifie alors de manière exacte si ce sous-graphe est 3-colorable, et il retourne pour le graphe global la même réponse que pour le sous-graphe.

Alon et Krielevich ont montré qu'avec une probabilité de 2/3, cette réponse était juste.

Deux autres problèmes importants consiste à savoir si le graphe d'entrée est sans graphe sans triangle[6] et s'il est biparti[7].

Le test de propriété peut aussi être utilisé pour estimer les propriétés de fonctions (monotonie, linéarité...), ou d'ensembles divers : est-ce qu'un ensemble de points est recouvrable par un nombre donné de boules, en quelle langue est écrit un texte... On parle en particulier de tests de propriétés algébriques, lorsque les objets considérés sont des structures algébriques comme des groupes ou des espaces vectoriels[8].

Une variante a également émergé, dans laquelle l'objet étudié est une distribution de probabilité ${\displaystyle D}$ sur un ensemble ${\displaystyle {\mathcal {X}}}$, et le but est de déterminer, ayant accès à des observations indépendantes de ${\displaystyle D}$, si cette dernière satisfait une certaine propriété (telle qu'être uniforme, avoir une faible entropie, ou bien avoir une densité de probabilité décroissante ...)[9].