Conjecture d'Aanderaa-Karp-Rosenberg

Pour les algorithmes déterministes, Rosenberg (1973) a conjecturé que pour toutes les propriétés de graphe non triviales sur ${\displaystyle n}$ sommets, décider si un graphe possède cette propriété a une complexité en ${\displaystyle \Omega (n^{2})}$. 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.

Un graphe scorpion. L'un des trois sommets rouges du chemin est adjacent à tous les autres sommets et les deux autres sommets rouges n'ont pas d'autres adjacences.

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 ${\displaystyle O(n)}$ requêtes à tester. Dans ce contexte, un puits dans un graphe orienté est un sommet de degré entrant ${\displaystyle n-1}$ et de degré sortant nul. L'existence d'un puits peut être testée en moins de ${\displaystyle 3n}$ requêtes[1]. Une autre propriété de graphes non orientés qui peut également être testée en ${\displaystyle O(n)}$ requêtes est la propriété d'être un graphe scorpion, propriété décrite pour la première fois dans Best, van Emde Boas et Lenstra (1974). 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 ${\displaystyle \Omega (n^{2})}$ requêtes. Cette conjecture a été résolue positivement par Rivest et Vuillemin (1975) qui montrent qu'au moins ${\displaystyle {\tfrac {1}{16}}n^{2}}$ requêtes sont nécessaires pour tester toute propriété de graphe monotone non triviale. La borne a été améliorée en ${\displaystyle {\tfrac {1}{9}}n^{2}}$ par Kleitman et Kwiatkowski (1980), puis en ${\displaystyle \left({\tfrac {1}{4}}-\varepsilon \right)n^{2}}$ (pour tout ${\displaystyle \varepsilon >0}$) par Kahn, Saks et Sturtevant (1984), en ${\displaystyle {\bigl (}{\tfrac {8}{25}}-\varepsilon {\bigr )}n^{2}}$ par Korneffel et Triesch (2010), et en ${\displaystyle \left({\tfrac {1}{3}}-\varepsilon \right)n^{2}}$ par Scheidweiler et Triesch (2013).

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 ${\displaystyle n}$ 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 ${\displaystyle n(n-1)/2}$ 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 ${\displaystyle n}$. La conjecture est démontrée dans le cas où ${\displaystyle n}$ est une puissance première par Kahn, Saks et Sturtevant (1984) 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 Yao (1988). Il a également été démontré que les propriétés fermées par passage aux mineurs sont évasives pour les grandes valeurs de ${\displaystyle n}$ (Chakrabarti, Khot et Shi 2001).

Dans l'article de Kahn, Saks et Sturtevant (1984), 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 ${\displaystyle n}$ est une puissance primordiale par Lovász et Young (2002).

Richard Karp a également conjecturé que ${\displaystyle \Omega (n^{2})}$ 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 ${\displaystyle {\tfrac {1}{4}}n^{2}}$ requêtes. Une borne inférieure linéaire (c'est-à-dire en ${\displaystyle \Omega (n)}$) 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 Yao (1991), qui a montré que ${\displaystyle \Omega {\bigl (}n(\log n)^{1/12}{\bigr )}}$ requêtes sont nécessaires. Cette borne a été améliorée par King (1991) en ${\displaystyle \Omega (n^{5/4})}$, puis par Hajnal (1991) en ${\displaystyle \Omega (n^{4/3})}$. La meilleure borne inférieure connue en 2007 (parmi les bornes valables pour toutes les propriétés monotones) est ${\displaystyle \Omega \left(n^{4/3}(\log n)^{1/3}\right)}$, donnée par Chakrabarti et Khot (2007).

Certains résultats donnent des bornes inférieures qui sont déterminées par ce qui est appelé la probabilité critique ${\displaystyle p}$ de la propriété de graphe monotone considérée. La probabilité critique ${\displaystyle p}$ est définie comme étant le nombre unique ${\displaystyle p}$ dans l'intervalle ${\displaystyle [0,1]}$ tel qu'un graphe aléatoire ${\displaystyle G(n,p)}$, obtenu en choisissant aléatoirement si chaque arête existe, indépendamment des autres arêtes, avec probabilité ${\displaystyle p}$ par arête, possède cette propriété avec une probabilité égale à ${\displaystyle {\tfrac {1}{2}}}$. Friedgut, Kahn et Wigderson (2002) ont montré que toute propriété monotone avec probabilité critique ${\displaystyle p}$ requiert

${\displaystyle \Omega \left(\min \left\{{\frac {n}{\min(p,1-p)}},{\frac {n^{2}}{\log n}}\right\}\right)}$

requêtes. Pour le même problème, O'Donnell et al. (2005) ont montré une borne inférieure en ${\displaystyle \Omega (n^{4/3}/p^{1/3})}$.

Comme dans le cas déterministe, il existe de nombreuses propriétés particulières pour lesquelles une borne inférieure en ${\displaystyle \Omega (n^{2})}$ 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 ${\displaystyle \Omega (n^{3/2})}$ , due à Gröger (1992).

Pour la complexité des requêtes quantiques à erreur bornée, la meilleure borne inférieure connue est ${\displaystyle \Omega {\bigl (}n^{2/3}(\log n)^{1/6}{\bigr )}}$, 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 ${\displaystyle \Omega (n)}$, contrairement au cas classique, grâce à l'algorithme de Grover qui donne une algorithme en ${\displaystyle O(n)}$ 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 ${\displaystyle \Omega (n)}$, 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 ${\displaystyle \Omega (n^{3/2})}$, et même certaines propriétés avec une borne inférieure en ${\displaystyle \Omega (n^{2})}$. Par exemple, la propriété monotone de la non planarité nécessite ${\displaystyle \Theta (n^{3/2})}$ requêtes[2] 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 ${\displaystyle \Theta (n^{2})}$ requêtes[3].