Problème de la clique

On peut trouver une clique maximale grâce à un algorithme glouton en temps linéaire[16]. En commençant par une clique arbitraire (par exemple, n'importe quel sommet unique ou même l'ensemble vide), augmentez la clique actuelle un sommet à la fois en faisant une boucle sur les sommets restants du graphe. Pour chaque sommet v que cette boucle examine, ajoutez v à la clique si v est adjacent à chaque sommet qui est déjà dans la clique, et rejetez v dans le cas contraire. En raison de la facilité de trouver des cliques maximales et de leur petite taille potentielle, plus d'attention a été accordée au problème algorithmique beaucoup plus difficile de trouver une clique maximum ou une plus grande qu'une taille donnée. Cependant, certaines recherches en algorithmique parallèle ont toutefois étudié le problème de la recherche d'une clique maximale. En particulier, le problème de la recherche de la première clique maximale lexicographique (celle trouvée par l'algorithme ci-dessus) s'est avéré complet pour la classe des fonctions de temps polynomiales (FP) . Ce résultat implique qu'il est peu probable que le problème puisse être résolu dans la classe de complexité parallèle NC.[17]

On peut tester si un graphe G contient une clique de taille k, et trouver une telle clique, en utilisant un algorithme de recherche exhaustive . Cet algorithme examine chaque sous-graphe avec k sommets et vérifie s'il forme une clique. Cela s'effectue en temps ${\displaystyle O(n^{k}k^{2})}$, tel qu'exprimé en utilisant la notation O. En effet, il y a ${\displaystyle O(n^{k})}$ sous-graphes à vérifier, chacun d'entre eux ayant ${\displaystyle O(k^{2})}$ arêtes dont la présence dans le graphe G doit être vérifiée. Ainsi, le problème peut être résolu en temps polynomial à condition que k soit une constante fixe. Cependant, lorsque k n'a pas de valeur fixe, et est une variable du problème, le temps est exponentiel.[18]

Le cas non trivial le plus simple du problème de recherche de clique est de trouver un triangle dans un graphe, ou de déterminer de manière équivalente si le graphe est sans triangle . Dans un graphe G avec m arêtes, il peut y avoir au plus Θ(m^3/2) triangles (en utilisant la notation grand thêta pour indiquer que cette borne est serrée). Le pire des cas pour cette formule se produit lorsque G est lui-même une clique. Par conséquent, les algorithmes pour lister tous les triangles doivent prendre au moins Ω(m^3/2) temps dans le pire des cas (en utilisant la notation grand oméga ), et des algorithmes sont connus qui correspondent à cette limite de temps.[19] Par exemple, Chiba & Nishizeki (1985) décrivent un algorithme qui trie les sommets dans l'ordre du plus haut degré au plus bas, puis itère à travers chaque sommet v de la liste triée, à la recherche de triangles qui incluent v et n'incluent aucun sommet précédent dans le liste. Pour ce faire, l'algorithme marque tous les voisins de v, recherche à travers tous les arêtes incidentes à un voisin de v, produisant un triangle pour chaque arête qui a deux extrémités marquées, puis supprime les marques et supprime v du graphe. Comme le montrent les auteurs, le temps de cet algorithme est proportionnel à l' arboricité du graphe (notée a(G) ) multipliée par le nombre d'arêtes, qui est ${\displaystyle O(m\ a(G))}$ . L'arboricité étant au plus égale à ${\displaystyle O(m\ a(G))}$, cet algorithme s'exécute au temps ${\displaystyle O(m^{\frac {3}{2}})}$ . Plus généralement, toutes les k -cliques peuvent être listées par un algorithme similaire qui prend un temps proportionnel au nombre d'arêtes multiplié par l'arboricité à la puissance (k − 2) . Pour les graphes d'arboricité constante, tels que les graphes planaires (ou en général les graphes de toute famille de graphes mineurs fermés non triviale), cet algorithme prend un temps ${\displaystyle O(m\ a(G))}$, ce qui est optimal car il est linéaire dans la taille de l'entrée[20].

Si l'on désire un seul triangle, ou l'assurance que le graphe est sans triangle, des algorithmes plus rapides sont possibles. Comme l'observe Itai & Rodeh (1978), le graphe contient un triangle si et seulement si sa matrice d'adjacence et le carré de sa matrice d'adjacence contiennent des entrées non nulles dans la même cellule. Par conséquent, des techniques de multiplication matricielle rapide telles que l' algorithme Coppersmith – Winograd peuvent être appliquées pour trouver des triangles dans le temps ${\displaystyle O(n^{2.376})}$ . Alon, Yuster & Zwick (1994) ont utilisé la multiplication matricielle rapide pour améliorer l'algorithme en ${\displaystyle O(m^{\frac {3}{2}})}$ pour trouver des triangles en ${\displaystyle O(m^{1.41})}$ . Ces algorithmes basés sur la multiplication matricielle rapide ont également été étendus aux problèmes de recherche de k -cliques pour des valeurs de k plus grandes.[21] [22] [23] [24] [25]

D'après un résultat de Moon & Moser (1965), chaque graphe de taille ${\displaystyle n}$ a au plus 3^n/3 cliques maximales. Elles peuvent être listées par l' algorithme de Bron – Kerbosch, un algorithme de retour arrière créé par Bron & Kerbosch (1973) . Le sous-programme récursif principal de cet algorithme a trois arguments: une clique partiellement construite (non maximale), un ensemble de sommets candidats qui pourraient être ajoutés à la clique, et un autre ensemble de sommets qui ne devraient pas être ajoutés (car cela conduirait à une clique déjà trouvée). L'algorithme essaie d'ajouter les sommets candidats un par un à la clique partielle, en effectuant un appel récursif pour chacun. Après avoir essayé chacun de ces sommets, il le déplace vers l'ensemble des sommets qui ne doivent plus être ajoutés. On peut montrer que des variantes de cet algorithme ont un temps d'exécution dans le pire des cas en ${\displaystyle O(3^{n/3})}$, correspondant au nombre de cliques qui pourraient avoir besoin d'être listées. [26] Par conséquent, cela fournit une solution optimale dans le pire des cas au problème de la liste de toutes les cliques maximales. De plus, l'algorithme de Bron – Kerbosch a été largement déclaré plus rapide en pratique que ses alternatives. [27]

Cependant, lorsque le nombre de cliques est significativement plus petit que celui du pire cas, d'autres algorithmes peuvent être préférables. Comme Tsukiyama et al. (1977) l'ont montré, il est également possible de lister toutes les cliques maximales dans un graphe dans un laps de temps qui est polynomial par clique générée. Un algorithme tel que le leur, dans lequel le temps d'exécution dépend de la taille de la sortie est appelé algorithme sensible à la sortie . Leur algorithme est basé sur les deux observations suivantes, reliant les cliques maximales du graphe G de départ aux cliques maximales d'un graphe G \ v formé en supprimant un sommet arbitraire v de G :

• Pour chaque clique maximale K de G \ v, soit K continue de former une clique maximale dans G, soit K ⋃ {v} forme une clique maximale dans G. Par conséquent, G a au moins autant de cliques maximales que G \ v.
• Chaque clique maximale dans G qui ne contient pas v est une clique maximale dans G \ v, et chaque clique maximale dans G qui contient v peut être formée à partir d'une clique maximale K dans G \ v en ajoutant v et en supprimant les non-voisins de v dans K.

En utilisant ces observations, on peut générer toutes les cliques maximales dans G par un algorithme récursif qui choisit v puis, pour chaque clique maximale K dans G \ v, produit à la fois K et la clique formée en ajoutant v à K et en supprimant les non-voisins de v . Cependant, certaines cliques de G peuvent être générées de cette manière à partir de plus d'une clique parente de G \ v, donc ils éliminent les doublons en conservant une clique dans G uniquement lorsque son parent dans G \ v est le maximum lexicographique parmi toutes les cliques parentes possibles. Sur la base de ce principe, ils montrent que toutes les cliques maximales dans G peuvent être générées en temps ${\displaystyle O(mn)}$ par clique, où m est le nombre d'arêtes dans G et n est le nombre de sommets. Chiba & Nishizeki (1985) l' améliorent à O(ma) par clique, où a est l'arboricité du graphe donné. Makino & Uno (2004) proposent un algorithme alternatif sensible à la sortie basé sur une multiplication matricielle rapide. Johnson & Yannakakis (1988) montrent qu'il est même possible de lister toutes les cliques maximales dans l' ordre lexicographique avec un retard polynomial par clique. Cependant, le choix de l'ordre est important pour l'efficacité de cet algorithme: pour l'inverse de cet ordre, il n'y a pas d'algorithme à retard polynomial sauf si P = NP .

Sur la base de ce résultat, il est possible de lister toutes les cliques maximales en temps polynomial, pour des familles de graphes dans lesquelles le nombre de cliques est polynomialement borné. Ces familles comprennent les graphes cordaux, les graphes complets, les graphes sans triangle, les graphes d'intervalles, les graphes de boxicité (en) bornée et les graphes planaires . [28] En particulier, les graphes planaires ont ${\displaystyle O(n)}$ cliques, de taille au plus constante, qui peuvent être listées en temps linéaire. Il en va de même pour toute famille de graphe clairsemés (ayant un nombre d'arêtes au plus constant multiplié par le nombre de sommets) fermée sous l'opération de prise de sous-graphes.[20]^,[29]

Il est possible de trouver une clique maximum, ou sa taille, d'un graphe arbitraire à n sommets dans le temps ${\displaystyle O(3^{n/3})=O(1.4422^{n})}$ en utilisant l'un des algorithmes décrits ci-dessus pour lister toutes les cliques maximales dans le graphe et celle de cardinal maximum. Cependant, pour cette variante du problème de clique, de meilleures limites de temps dans le pire des cas sont possibles. L'algorithme de Tarjan & Trojanowski (1977) résout ce problème en temps ${\displaystyle O(2^{n/3})=O(1.2599^{n})}$ . Il s'agit d'un algorithme de retour arrière récursif similaire à celui de l' algorithme de Bron-Kerbosch, mais il est capable d'éliminer certains appels récursifs lorsqu'il peut être démontré que les cliques trouvées dans l'appel seront sous-optimales. Jian (1986) a amélioré le temps à ${\displaystyle O(2^{0.304n})=O(1.2346^{n})}$, et Robson (1986) à ${\displaystyle O(2^{0.276n})=O(1.2108^{n})}$, au détriment d'une plus grande complexité spatiale. L'algorithme de Robson combine un algorithme de retour arrière similaire (avec une analyse de cas plus compliquée) et une technique de programmation dynamique dans laquelle la solution optimale est précalculée pour tous les petits sous-graphes connectés du graphe complémentaire . Ces solutions partielles sont utilisées pour raccourcir la récursivité de retour arrière. L'algorithme le plus rapide connu aujourd'hui est une version raffinée de cette méthode par Robson (2001) qui s'exécute dans le temps ${\displaystyle O(2^{0.249n})=O(1.1888^{n})}$. [30]

Il y a également eu des recherches approfondies sur les algorithmes heuristiques pour résoudre les problèmes de clique maximum sans garanties sur le temps d'exécution dans le pire cas, basées sur des méthodes comprenant la séparation et évaluation[31], la recherche locale[32], les algorithmes gloutons[33], et la programmation par contraintes. [34] Les méthodologies de calcul non standards qui ont été suggérées pour trouver des cliques comprennent le calcul ADN et le calcul quantique adiabatique . [35] Le problème de clique maximum a fait l'objet d'un défi de mise en œuvre parrainé par DIMACS (en) en 1992–1993, [36] dont la collection de graphes utilisés comme points de repère pour le défi est accessible au public.

Dans ce graphe de permutation, les cliques maximums correspondent aux sous-suites décroissantes les plus longues, (4,3,1) et (4,3,2) dans la permutation ici définie.

Les graphes planaires, et d'autres familles de graphes clairsemés, ont été discutés ci-dessus: ils ont des cliques maximales linéairement nombreuses, de taille bornée, qui peuvent être listées en temps linéaire[20]. En particulier, pour les graphes planaires, toute clique peut avoir au plus quatre sommets, selon le théorème de Kuratowski[37] .

Les graphes parfaits sont définis comme étant les graphes qui vérifie la propriété d'avoir leur nombre de clique égal à leur nombre chromatique, et dont chaque sous-graphes induit vérifie aussi cette propriété. Pour des graphes parfaits, il est possible de trouver une clique maximum en temps polynomial, en utilisant un algorithme basé sur une programmation semi-définie . [38] Cependant, cette méthode est complexe et non combinatoire, et des algorithmes de recherche de cliques spécialisés ont été développés pour de nombreuses sous-familles de graphes parfaits. [39] Dans les graphes complémentaires des graphes bipartis, le théorème de Kőnig permet de résoudre le problème de la clique maximum en utilisant des techniques de couplage . Dans une autre famille de graphes parfaits, les graphes de permutation, une clique maximum est une sous-suite décroissante la plus longue de la permutation définissant le graphe et peut être trouvée en utilisant des algorithmes connus pour le problème de sous-suite décroissante la plus longue. Inversement, chaque instance du problème de sous-suite décroissante la plus longue peut être décrite de manière équivalente comme un problème de recherche d'une clique maximum dans un graphe de permutation. Even, Pnueli & Lempel (1972) fournissent un algorithme alternatif pour les cliques maximales dans les graphes de comparabilité, une famille plus large de graphes parfaits qui inclut les graphes de permutation[40]. Cet algorithme s'exécute en temps quadratique. [41] Dans les graphes cordaux, les cliques maximales peuvent être trouvées en listant les sommets dans un ordre d'élimination, et en vérifiant les voisinages de clique de chaque sommet dans cet ordre[42].

Dans certains cas, ces algorithmes peuvent également être étendus à d'autres familles de graphes non parfaits. Par exemple, dans un graphe circulaire, le voisinage de chaque sommet est un graphe de permutation, donc une clique maximum dans un graphe circulaire peut être trouvée en appliquant l'algorithme de graphe de permutation à chaque voisinage[43]. De même, dans un graphe de disque unitaire (avec une représentation géométrique connue), il existe un algorithme en temps polynomial pour les cliques maximums basé sur l'application de l'algorithme sur les complémentaires de graphes bipartis aux voisinages partagés par des paires de sommets. [44]

Le problème algorithmique de trouver une clique maximum dans un graphe aléatoire tiré du modèle Erdős – Rényi (dans lequel chaque arête apparaît avec une probabilité 1/2, indépendamment des autres arêtes) a été suggéré par Karp (1976) . Étant donné que la clique maximum dans un graphe aléatoire a une taille logarithmique avec une probabilité élevée, elle peut souvent être trouvée par une recherche par force brute dans le temps ${\displaystyle 2^{O(log^{2}(n))}}$ . Il s'agit d'une limite temporelle quasi polynomiale . [45] Bien que le nombre de cliques de ces graphes soit généralement très proche de 2 log₂n, des algorithmes gloutons simples ainsi que des techniques d'approximation aléatoire plus sophistiquées ne trouvent que des cliques de taille log₂n, deux fois moins grandes. Le nombre de cliques maximales dans de tels graphes est avec une probabilité élevée exponentielle en log²n, ce qui empêche les méthodes qui répertorient toutes les cliques maximales de s'exécuter en temps polynomial. [46] En raison de la difficulté de ce problème, plusieurs auteurs ont étudié le problème de la clique plantée, le problème de la clique sur des graphes aléatoires qui ont été augmentés en ajoutant de grandes cliques. [47] Alors que les méthodes spectrales [48] et la programmation semi-définie [49] peuvent détecter les cliques cachées de taille ${\displaystyle \Omega ({\sqrt {n}})}$, aucun algorithme en temps polynomial n'est actuellement connu pour détecter celles de taille ${\displaystyle o({\sqrt {n}})}$ (exprimées en utilisant la notation o ). [50]

Plusieurs auteurs ont envisagé des algorithmes d'approximation qui tentent de trouver une clique ou un ensemble indépendant qui, bien que non maximum, a une taille aussi proche du maximum que l'on peut trouver en temps polynomial. Bien qu'une grande partie de ce travail se soit concentrée sur des ensembles indépendants dans des graphes clairsemés, un cas qui n'a pas de sens pour le problème de la clique complémentaire, il y a également eu des travaux sur des algorithmes d'approximation pour des graphes non nécessairement clairsemés.[51]

Feige (2004) décrit un algorithme en temps polynomial qui trouve une clique de taille Ω((log n/log log n)²) dans n'importe quel graphe contenant une clique de taille Ω(n/log^kn) pour n'importe quelle constante ${\displaystyle k}$. En utilisant cet algorithme quand la taille de la clique maximum est entre n/log n et n/log³n, en utilisant un algorithme différent (de Boppana & Halldórsson (1992) ) pour les graphes dont les cliques maximums sont plus grandes, et en utilisant une 2-clique quand les deux algorithmes échouent, Feige fournit un algorithme d'approximation qui trouve une clique de taille proche du maximum à un facteur O(n(log log n)²/log³n). Même si le taux d'approximation de cet algorithme est faible, c'est le meilleur connu à ce jour[52]. Les résultats portant sur la dureté d'approximation décrits ci-après suggèrent qu'il ne peut pas exister d'algorithme d'approximation de ratio significativement meilleur que linéaire.

L'instance de satisfaction 3-FNC (x ∨ x ∨ y) ∧ (~ x ∨ ~ y ∨ ~ y) ∧ (~ x ∨ y ∨ y) réduite à une instance de Clique. Les sommets verts forment une 3-clique et correspondent à une affectation satisfaisante.

Le problème de la décision de clique est NP-complet . C'était l'un des 21 problèmes originaux de Richard Karp montré NP-complet dans son article de 1972 « Réductibilité parmi les problèmes combinatoires ». [53] Ce problème a également été mentionné dans l'article de Stephen Cook présentant la théorie des problèmes NP-complets[54]. En raison de la dureté du problème de décision, le problème de trouver une clique maximum est également NP-difficile. Si on pouvait le résoudre, on pourrait aussi résoudre le problème de décision, en comparant la taille de la clique maximum au paramètre de taille donné en entrée dans le problème de décision.

On passe en général par 3-SAT.

Certains problèmes NP-complets (tels que le problème du voyageur de commerce dans les graphes planaires ) peuvent être résolus dans le temps qui est exponentiel en une fonction sous-linéaire du paramètre de taille d'entrée n, significativement plus rapide qu'une recherche par force brute.[55] Cependant, il est peu probable qu'une telle limite temporelle sous-exponentielle soit possible pour le problème de clique dans des graphes arbitraires, car elle impliquerait des limites sous-exponentielles similaires pour de nombreux autres problèmes NP-complets standards. [56]

Un circuit monotone pour détecter une k-clique dans un graphe à n-sommets pour k = 3 et n = 4. Chaque entrée dans ce circuit code l'absence ou la présence d'une arête précise (celle en rouge) sur le graphe. Le circuit utilise une porte logique et interne pour détecter chaque potentielle k-clique.

La complexité de résolution du problème de la clique a été utilisé pour trouver plusieurs bornes inférieures en complexité de circuit. L’existence d’une clique d’une taille donnée est une propriété monotone de graphe, ce qui signifie que s’il existe une clique dans un graphe, alors il existera dans tous les sur-graphes du premier graphe. La monotonie de la propriété implique qu’il existe un circuit monotone n’utilisant que des portes logiques ou et et permettant de résoudre le problème de décisions d’existence d’une clique de taille fixée. Cependant la taille de ces circuits est plus que polynomiale en la taille de la clique et en le nombre d’arêtes : il est exponentiel en la racine cubique du nombre d’arêtes[57]. Même si on autorise un petit nombre de portes non la complexité reste plus que polynomiale[58]. De plus la profondeur d’un circuit monotone résolvant le problème de la clique avec un nombre borné de fan-in doit être au moins polynomiale en la taille de la clique[59].

La complexité paramétrée est l' étude théorique de la complexité de problèmes qui sont naturellement équipés d'un petit paramètre entier k et pour lesquels le problème devient plus difficile à mesure que k augmente, comme la recherche de k -cliques dans les graphes. Un problème est dit traitable à paramètre fixé s'il existe un algorithme pour le résoudre sur des entrées de taille n, et une fonction f, telle que l'algorithme s'exécute au temps ${\displaystyle f(k)n^{O(1)}}$[60]. Autrement dit, il est traitable à paramètre fixé s'il peut être résolu en temps polynomial pour toute valeur fixe de k et de plus si l'exposant du polynôme ne dépend pas de k .

Pour trouver des k-cliques, l'algorithme de recherche par force brute a un temps d'exécution O(n^kk²) . Comme l'exposant de n dépend de k, cet algorithme n'est pas traitable à paramètre fixe. Bien qu'il puisse être amélioré par une multiplication matricielle rapide, le temps d'exécution a toujours un exposant linéaire en k. Ainsi, bien que le temps d'exécution des algorithmes connus pour le problème de clique soit polynomial pour tout k fixe, ces algorithmes ne suffisent pas pour la traitabilité à paramètre fixé. Downey & Fellows (1995)[61] ont défini une hiérarchie de problèmes paramétrés, la hiérarchie W, dont ils ont supposé qu'elle n'avait pas d'algorithmes traitables à paramètres fixes. Ils ont prouvé que l'ensemble indépendant (ou, de manière équivalente, clique) est difficile pour le premier niveau de cette hiérarchie, W [1] . Ainsi, selon leur conjecture, la clique n'a pas d'algorithme traitable à paramètre fixe. De plus, ce résultat fournit la base des preuves de la dureté W [1] de nombreux autres problèmes, et sert ainsi d'analogue au théorème de Cook-Levin pour la complexité paramétrée. [18]

Chen et al. (2006)[62] ont montré que trouver des k-cliques ne peut pas être fait en temps n^o(k) sauf si l'hypothèse du temps exponentiel est invalide. Encore une fois, c'est un argument en faveur de l'intraitabilité à paramètre fixé.[63]

Bien que les problèmes d'énumération des cliques maximales ou de recherche de cliques maximums soient peu susceptibles d'être traitables à paramètre k fixé, ils peuvent être traitables à paramètre fixé pour d'autres paramètres de complexité d'instance. Par exemple, les deux problèmes sont connus pour être résolus à paramètre fixé lorsqu'ils sont paramétrés par la dégénérescence du graphe d'entrée[29].

Un graphe des relations de compatibilité pour des échantillons de 2 bits sur des preuves de 3 bits. Chaque clique maximale dans ce graphe représente toutes les manières d’échantillonner 3 bits. La preuve d'inaproximabilité du problème de la clique utilise des sous-graphes de graphes construits de même manière pour un plus grand nombre de bits.

De faibles résultats laissant à penser que le problème de la clique soit dur à approximer est connu depuis longtemps. Garey et Johnson en 1978[64] ont observé que parce que le nombre de petites cliques est NP-difficile à calculer il ne peut y avoir un schéma d'approximation en temps polynomial. Si une approximation trop précise existait, arrondir le nombre obtenu par le schéma d'approximation à l'entier le plus proche donnerait le nombre précis de cliques.

Cependant, ce n'est qu'au début des années 1990 que d'autres résultats ont été prouvés lorsque des chercheuses et chercheurs ont fait le lien entre l'approximation du problème de la clique maximum et les preuves vérifiables de manière probabiliste. Elles et ils ont utilisé cette connexion pour montrer la dureté d'approximation du problème de la clique maximum[3][65] [66][67]. Après de nombreuses améliorations, il est désormais connu que pour tout ${\displaystyle \epsilon >0}$, il ne peut exister un algorithme en temps polynomial approximant la clique maximum avec un meilleur facteur qu'un ${\displaystyle O\left(n^{1-\epsilon }\right)}$ à moins que P=NP.

L'idée générale de ces résultats est que l'on peut créer un graphe représentant un système de preuves vérifiables de manière probabiliste pour un problème NP-complet comme le problème de satisfiabilité booléenne. Dans un système de preuves vérifiables de manière probabiliste, une preuve est représentée par une séquence de bits. Une instance du problème de satisfiabilité doit avoir une preuve valide si et seulement si l'instance est satisfiable. La preuve est vérifiée et examinée par un algorithme qui, après un temps de calcul polynomial sur l'instance du problème, choisit d'examiner un petit nombre de positions aléatoirement choisies dans la chaine de caractère de la preuve. En fonction de la valeur trouvée sur cet échantillon de bits, l'algorithme acceptera ou non la preuve sans avoir à regarder les autres bits. Les faux négatifs ne sont pas autorisés : une preuve valide doit toujours être acceptée. Par contre, une preuve invalide peut parfois être acceptée. Cependant, pour chaque preuve invalide, la probabilité que l'algorithme l'accepte se doit d'être basse[68].

Pour transformer un système de preuve vérifiable de manière probabiliste en une instance du problème de la clique, on forme un graphe avec comme sommets chaque portion de bits pouvant être choisie aléatoirement. Un sommet peut donc être représenté par une séquence de bits de la même taille que celle de la preuve avec des 0 ou des 1 sur les caractères examinés par l'algorithme et des $ pour les autres. Deux sommets sont reliés si les deux sommets ont les mêmes codes (0 ou 1) dans les positions que les deux examinent (i.e. là où il n'y a aucun $ dans les deux sommets). Chaque portion de preuve (valide ou invalide) correspond à une clique. Une de ces cliques est grande si et seulement si elle correspond à une portion de preuve que beaucoup d'algorithmes acceptent. Si l'instance originale du problème de satisfiabilité est satisfiable alors il aura une portion de preuve valide qui sera acceptée par tous les algorithmes et cette portion correspondra à la clique maximale dans le graphe. Au contraire, si ce n'est pas le cas alors toutes les portions de preuves sont invalides, et donc chaque portion de preuve sera acceptée par un très faible nombre d'algorithmes ce qui entraine le fait que toutes les cliques soient petites. C'est pourquoi, s'il existait un algorithme permettant de distinguer les graphes avec de grandes cliques et les graphes avec que des petites cliques, ou alors s'il existait un graphe approximant suffisamment bien le problème de la clique maximale, alors utiliser cet algorithme permettrait de distinguer en temps polynomial les instances satisfiables et celles non satisfiables, ce qui est impossible à moins que P=NP.[68]

• Portail de l'informatique théorique