- Testeur de propriété
-
En mathématiques, un testeur de propriété est un algorithme probabiliste qui a pour objectif de déterminer si un objet donné (un graphe, ou une fonction par exemple) possède une propriété fixée.
Sommaire
Définition formelle
Soit E un ensemble, et d une distance sur cet ensemble. Soit F un sous-ensemble de E, qu'on appelle propriété. Un testeur de propriété pour F est un algorithme qui, prenant entrée un élément x de E et un paramètre de distance l :
- accepte x avec une probabilité p > 1 / 2 si x est dans F.
- rejette x avec une probabilité p' > 1 / 2 si d(x,F) > l.
- peut renvoyer n'importe quel résultat avec une probabilité quelconque si 0 < d(x,F) < l.
Si p ou p' vaut 1, l'algorithme est dit à erreur unilatérale. Sinon, il est dit à erreur bilatérale (Bien qu'il n'y ait pas de termes officiels français. En anglais, on parle d'algorithme with a "one-sided" or "two-sided" error .)
Intérêt
Comme nous le voyons au niveau du résultat, ces algorithmes ne sont pas des algorithmes exacts. Cependant, en se permettant d'avoir parfois un résultat faux, il est parfois possible d'avoir une "réponse probable" bien plus rapidement qu'avec un algorithme exact. De plus, dans le cas des algorithmes à erreur unilatérale, on peut parfois avoir une réponse exacte dans un temps très court (parfois même constant, et donc indépendant de la taille du problème en entrée).
Historique
Le concept de test de propriété est relativement récent. Bien qu'il soit relié à d'autres formes d'approximation, notamment les PCPs, on considère que le test de propriété pour des fonctions a été formulé explicitement pour la première fois par Rubinfeld et Sudan[1] dans le cadre du test de fonctions. Dans le cadre du test de propriété pour des graphes, le premier article à explicitement définir ces notions a été publié par Goldreich et Ron[2].
Depuis, de nombreux articles ont été publiés. Notamment, Alon (en) et al.[3] ont complètement caractérisé l'ensemble des propriétés de graphes testables efficacement (i.e en temps constant).
Exemples
Un ensemble particulièrement utilisé pour le test de propriété est celui des graphes finis. Pour simplifier, nous prendrons les graphes finis simples non orientés.
Nous choisissons comme ensemble F 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[4].
Exemple détaillé
Bien que la démonstration de la validité de l'algorithme ci-dessus soit compliquée, l'algorithme en lui-même est un exemple très générique de testeur de propriété. Nous allons donc le détailler afin de donner un exemple concret de testeur de propriétés.
L'algorithme reçoit en entrée un graphe G et un paramètre de distance l. De plus, la distance choisie est telle que si le graphe G possède n sommets, il sera à une distance l de F s'il faut lui enlever ln² arêtes pour qu'il soit dans F.
L'algorithme sélectionne aléatoirement 108ln(k)/l² du graphe 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 complet 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.
D'autres applications
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 …
Limites
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[5].
Bibliographie
- (en) Ronitt Rubinfeld et Sudan, « Robust characterization of polynomials with applications to program testing », dans SIAM Journal on Computing, vol. 25, no 2, février 1996, p. 252-271
- (en) Goldreich et Ron, « Property testing and its connection to learning and approximation », dans JACM, 1998
- (en) Alon, Fischer et Newman, « A combinatorial characterization of the testable graph properties: it's all about regularity », dans SIAM Journal on Computing, vol. 39, no 1, 2009, p. 251-260 [texte intégral (page consultée le 24 janvier 2011)]
- (en) Noga Alon et Krivelevich, « Testing k-colorability », dans SIAM Journal on Discrete Mathematics, vol. 15, no 2, février 2002 [texte intégral (page consultée le 21 janvier 2011)]
- (en) Kaufman, Krielevich et Ron, « Tight bounds for testing bipartiteness in general graphs », dans SIAM journal on computing, vol. 33, no 6, 2004, p. 1441-1483 (ISSN 0097-5397)
Wikimedia Foundation. 2010.
