Conjecture d'Aanderaa-Karp-Rosenberg

En informatique théorique, la conjecture dAanderaa-Karp-Rosenberg (aussi connue sous le nom de conjecture dAanderaa-Rosenberg ou conjecture de l'évasion) est un ensemble de conjectures concernant le nombre de questions de la forme « existe-t-il  une arête entre le sommet  et sommet  ? » dans un graphe auxquelles il faut répondre pour déterminer si oui ou non un graphe non orienté possède une propriété donnée telle que la planarité ou le caractère biparti . Elles portent les noms de Stål Aanderaa, Richard M. Karp et Arnold L. Rosenberg. La conjecture affirme que, pour une large classe de propriétés, tout algorithme pour déterminer si un graphe possède une de ces propriétés, aussi élaboré soit-il, peut être amené à examiner toute paire de sommets avant de donner sa réponse. Une propriété satisfaisant cette conjecture est dite évasive.

Description 

La conjecture d'Aanderaa-Rosenberg stipule que tout algorithme déterministe doit tester, dans le pire des cas, au moins une fraction constante de toutes les paires de sommets, pour déterminer une propriété de graphe monotone non triviale ; dans ce contexte, une propriété est dite monotone si elle reste vraie lorsque des arêtes sont ajoutées ; ainsi;, la planarité n'est pas monotone, mais la non-planarité est monotone. Une version plus forte de cette conjecture, appelée la conjecture d'évitement ou conjecture d'Aanderaa-Karp-Rosenberg, stipule qu'exactement  tests sont nécessaires. Des versions du problème pour les  algorithmes randomisés et les algorithmes quantiques ont également été formulées et étudiées.

La conjecture déterministe d'Aanderaa-Rosenberg a été prouvée par , mais la conjecture plus forte d'Aanderaa–Karp–Rosenberg est encore non résolue. De plus, il existe un grand écart entre la borne inférieure conjecturée et la borne inférieure prouvée pour la complexité des requêtes aléatoires et quantiques.

Un exemple 
La propriété d'être non vide, c'est-à-dire d'avoir au moins une arête, est une propriété monotone, car l'ajout d'une autre arête à un graphe non vide produit un autre graphe non vide. Il existe un algorithme simple pour tester si un graphe est non vide : on parcourt toutes les paires de sommets, et on teste si une paire est connectée par une arête. Si on trouve une arête, le graphe n'est pas vide, et si le parcours se termine sans avoir trouvé d'arêtes, le graphe est vide. Pour certains graphes, comme  les graphes complets, cet algorithme se termine rapidement, sans avoir à tester chaque paire de sommets, mais sur le graphe vide, il faut tester toutes les paires possibles avant de pouvoir conclure. Par conséquent, la complexité de cet algorithme est en  , car dans le pire des cas, l'algorithme doit effectuer  essais.

L'algorithme ci-dessus n'est pas la seule méthode possible pour tester si un graphe n'est pas vide, mais la conjecture d'Aanderaa-Karp-Rosenberg dit que tout algorithme déterministe pour tester qu'un graphe n'est pas vide la même complexité de requêtes dans le pire des cas, à savoir . Autrement dit, la propriété d'être non vide est évasive. Pour cette propriété, le résultat est facile à prouver directement : si un algorithme n'effectue pas  tests, il ne peut pas distinguer le graphe vide d'un graphe qui a une arête reliant l'une des paires de sommets non testés, et il donne donc une réponse incorrecte sur l'un de ces deux graphes.

Définitions 
Formellement, une propriété de graphe est une fonction de la famille de tous les graphes dans l'ensemble  telle que deux graphes isomorphes ont la même valeur. Par exemple, la propriété de contenir au moins un sommet de degré deux est une telle propriété de graphe, mais la propriété que le premier des sommets est de degré deux ne l'est pas, car elle dépend de l'étiquetage du graphe (en particulier, cela dépend de quel sommet est le « premier » sommet). Une propriété de graphe est dite non triviale si elle n'attribue pas la même valeur à tous les graphes. Par exemple, la propriété d'être vide n'est pas triviale, car le graphe vide possède cette propriété, mais pas les graphes non vides. Une propriété de graphe est dite monotone si l'ajout d'arêtes ne modifie pas la propriété. Par exemple, la propriété d'être non planaire est monotone : un supergraphe (qui contient plus d'arêtes) d'un graphe non planaire est lui-même non planaire. En revanche, la propriété d'être un graphe régulier n'est pas monotone.

Complexité des requêtes 
La complexité déterministe d'une requête d'évaluation d'une fonction à  bits étiquetés  est le nombre de bits  qui doivent être lus, dans le pire des cas, par un algorithme déterministe qui évalue la fonction. Par exemple, si la fonction prend la valeur 0 lorsque tous les bits sont égaux à 0 et prend la valeur 1 sinon (comme la disjonction logique), alors sa complexité de requête déterministe est exactement  : en effet, dans le pire des cas, et quel que soit l'ordre dans lequel  on examine les entrées, il se peut que les  premier bits soient égaux à 0, et la valeur de la fonction dépend alors du dernier bit. Si un algorithme ne lit pas ce bit, la réponse peut être incorrecte (de tels arguments sont appelés arguments de l'adversaire).

La complexité randomisée  d'évaluation d'une fonction est définie de manière similaire, sauf que l'algorithme peut être randomisé. En d'autres termes, on peut lancer un dé et utiliser le résultat de ces lancers pour décider quels bits interroger et dans quel ordre. Cependant, l'algorithme randomisé doit toujours produire la bonne réponse pour toutes les entrées. Ces algorithmes sont les algorithmes de Las Vegas ;  les algorithmes de Monte Carlo, sont autorisés à faire des erreurs. La complexité des requêtes aléatoire peut être définie pour les algorithmes de Las Vegas et de Monte Carlo, mais la version aléatoire de la conjecture d'Aanderaa-Karp-Rosenberg concerne la complexité des requêtes à la Las Vegas.

La complexité des requêtes quantiques est la généralisation naturelle de la complexité des requêtes aléatoires, permettant des requêtes et des réponses quantiques. La complexité des requêtes quantiques peut aussi bien être définie pour les algorithmes de Monte Carlo ou algorithmes de Las Vegas.

Dans le contexte de la conjecture d'Aanderaa-Karp-Rosenberg, la fonction à évaluer est une propriété de graphe, et l'entrée peut être vue comme une chaîne binaire de taille , décrivant pour chaque paire de sommets s'il existe ou non une arête avec cette paire comme extrémités. La complexité de la requête de toute fonction sur cette entrée est au plus , car un algorithme qui fait les  requêtes peut lire l'intégralité de l'entrée et déterminer complètement le graphe d'entrée.

Complexité déterministe des requêtes 
Pour les algorithmes déterministes,  a conjecturé que pour toutes les propriétés de graphe non triviales sur  sommets, décider si un graphe possède cette propriété a une complexité en  . La condition de non-trivialité est requise pour éviter des questions triviales telles que « est-ce un graphe ? » auxquelles on peut répondre sans même poser une question.

La conjecture a été réfutée par Aanderaa, qui a présenté une propriété de graphe orienté (la propriété de « posséder un  sommet puits ») qui ne nécessitait que  requêtes à tester. Dans ce contexte, un puits dans un graphe orienté est un sommet de degré entrant  et de degré sortant nul. L'existence d'un puits peut être testée en moins de  requêtes. Une autre propriété de graphes non orientés qui peut également être testée en  requêtes est la propriété d'être un graphe scorpion, propriété décrite pour la première fois dans . Un graphe scorpion est un graphe contenant un chemin à trois sommets, de sorte qu'une extrémité du chemin est connectée à tous les sommets restants, tandis que les deux autres sommets du chemin n'ont pas d'arêtes incidentes autres que celles du chemin.

Aanderaa et Rosenberg ont ensuite formulé une nouvelle conjecture (dite la conjecture  d'Aanderaa-Rosenberg) qui affirme que décider si un graphe possède une propriété de graphe monotone non triviale nécessite  requêtes. Cette conjecture a été résolue positivement par  qui montrent qu'au moins  requêtes sont nécessaires pour tester toute propriété de graphe monotone non triviale. La borne a été améliorée en  par , puis en  (pour tout ) par , en  par , et en  par .

Richard Karp a énoncé une conjecture la plus forte, appelée la conjecture dévitement ou la conjecture d'Aanderaa-Karp-Rosenberg, selon laquelle « toute propriété de graphe monotone non triviale pour les graphes sur  sommets est évasive ». Une propriété est dite évasive si déterminer qu'un graphe donné possède cette propriété peut nécessiter toutes les  requêtes possibles. Cette conjecture dit que le meilleur algorithme pour tester une propriété monotone non triviale doit (dans le pire des cas) interroger toutes les arêtes possibles. Cette conjecture est encore ouverte, bien que plusieurs propriétés spéciales de graphes se soient révélées évasives pour tous . La conjecture est démontrée dans le cas où  est une puissance première par  en utilisant une approche topologique. La conjecture a également été prouvée pour toutes les propriétés monotones non triviales sur les graphes bipartis par . Il a également été démontré que les propriétés fermées par passage aux mineurs sont évasives pour les grandes valeurs de  .

Dans l'article de , la conjecture a également été généralisée aux propriétés de fonctions autres que celles portant sur les graphes, en supposant que toute fonction monotone non triviale faiblement symétrique est évasive. Ce cas est également résolu lorsque  est une puissance primordiale par .

Complexité des requêtes randomisées 
Richard Karp a également conjecturé que  requêtes sont nécessaires pour tester des propriétés monotones non triviales même si des algorithmes randomisés sont autorisés. Aucune propriété monotone non triviale n'est connue qui nécessite moins de  requêtes. Une borne inférieure linéaire (c'est-à-dire en ) sur toutes les propriétés monotones découle d'une relation très générale entre les complexités des requêtes randomisées et déterministes. La première borne inférieure super-linéaire pour toutes les propriétés monotones a été donnée par , qui a montré que  requêtes sont nécessaires. Cette borne a été améliorée par  en , puis par  en . La meilleure borne inférieure connue en 2007 (parmi les bornes valables pour toutes les propriétés monotones) est , donnée par .

Certains résultats donnent des bornes inférieures qui sont déterminées par ce qui est appelé la probabilité critique  de la propriété de graphe monotone considérée. La probabilité critique  est définie comme étant le nombre unique  dans l'intervalle   tel qu'un graphe aléatoire , obtenu en choisissant aléatoirement si chaque arête existe, indépendamment des autres arêtes, avec probabilité  par arête, possède cette propriété avec une probabilité égale à .  ont montré que toute propriété monotone avec probabilité critique  requiert 

requêtes. Pour le même problème,  ont montré une borne inférieure en .

Comme dans le cas déterministe, il existe de nombreuses propriétés particulières pour lesquelles une  borne inférieure en  est connue. De plus, des bornes inférieures meilleures sont connues pour plusieurs classes de propriétés de graphe. Par exemple, pour tester si le graphe a un sous-graphe isomorphe à un graphe donné (le problème de l'isomorphisme de sous-graphe), la meilleure borne inférieure connue est  , due à .

Complexité des requêtes quantiques 
Pour la complexité des requêtes quantiques à erreur bornée, la meilleure borne inférieure connue est , comme l'a observé Andrew Yao. Elle est obtenue en combinant la borne inférieure randomisée avec la méthode de l'adversaire quantique. La meilleure borne inférieure possible que l'on puisse espérer atteindre est , contrairement au cas classique, grâce à l'algorithme de Grover qui donne une  algorithme en  requêtes pour tester la propriété monotone d'être une graphe non vide. Comme dans le cas déterministe et randomisé, certaines propriétés sont connues pour avoir une borne inférieure en  , par exemple d'être non vide (ce qui découle de l'optimalité de l'algorithme de Grover) et la propriété de contenir un triangle. Certaines propriétés de graphes sont connues pour avoir une borne inférieure en  , et même certaines propriétés avec une  borne inférieure en . Par exemple, la propriété monotone de la non planarité nécessite  requêtes et la propriété monotone de contenir plus de la moitié du nombre possible d'arêtes (également appelée la fonction majoritaire) nécessite  requêtes.

Notes et références

Références

Bibliographie complémentaire 
.
  
 .
 .
 .
 .

Liens externes 

Combinatoire
Théorie des graphes
Conjecture