Problèmes algorithmiques complexes simplifiés par les théorèmes

Je cherche de bons exemples, où le phénomène suivant se produit: (1) Un problème algorithmique semble difficile, si vous voulez le résoudre en travaillant à partir des définitions et en utilisant uniquement les résultats standard. (2) En revanche, cela devient facile, si vous connaissez certains théorèmes (pas si standard).

Le but de ceci est d'illustrer pour les étudiants que l'apprentissage de plus de théorèmes peut être utile, même pour ceux qui sont en dehors du domaine théorique (tels que les ingénieurs logiciels, les ingénieurs en informatique, etc.). Voici un exemple:

Question: Étant donné les entiers , existe-t-il un graphe sommet (et si oui, en trouver un), tel que sa connectivité au sommet est , sa connectivité aux bords est et son degré minimum est ?n k l $n, k, l, d$$n$$k$$l$$d$

Notez que nous exigeons que les paramètres soient exactement égaux aux nombres donnés, ils ne sont pas seulement des bornes. Si vous souhaitez résoudre ce problème à partir de zéro, cela peut sembler assez difficile. D'un autre côté, si vous connaissez le théorème suivant (voir Théorie des graphes extrêmes par B. Bollobas), la situation devient très différente.

Théorème: Soit entiers. Il existe un graphe à sommets avec connectivité au sommet , connectivité aux bords et degré minimum , si et seulement si l'une des conditions suivantes est remplie:n k l $n, k, l, d$$n$$k$$l$$d$

• $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$ ,
• $1\leq 2d+2-n\leq k\leq l = d< n-1$
• $k=l=d=n-1.$

Ces conditions sont très faciles à vérifier, étant de simples inégalités entre les paramètres d'entrée, de sorte que la question de l'existence peut être résolue sans effort. De plus, la preuve du théorème est constructive, résolvant également le problème de construction. En revanche, ce résultat n'apparaît pas assez standard, de sorte que vous pouvez vous attendre à ce que tout le monde le sache.

Pouvez-vous fournir d'autres exemples dans cet esprit, où la connaissance d'un théorème (pas si standard) simplifie grandement une tâche?

Décider de l'isomorphisme de groupes simples , donné par leurs tables de multiplication. Le fait que cela puisse être fait en temps polynomial découle directement du fait que tous les groupes simples finis peuvent être générés par au plus 2 éléments, et actuellement la seule preuve connue de ce fait utilise la classification des groupes simples finis (peut-être le plus grand théorème - en termes d'auteurs, d'articles et de pages - jamais prouvé).

Si je comprends bien votre question, un exemple canonique serait de décider si un graphe a un circuit eulérien: équivalent à vérifier que G est connecté et que chaque sommet a un degré pair.$G$$G$

Cet après-midi, je lisais la Stringologie - la "vraie" théorie des cordes .

Problème: Si et y sont deux chaînes sur un alphabet, y a-t-il des entiers positifs m , n tels que x m = y n .$x$$y$$m, n$$x^m = y^n$

Théorème: Il existe des entiers positifs tels que x m = y n si et seulement si x y = y x .$m,n$$x^m = y^n$$xy = yx$

Trouver le nombre de racines réelles (distinctes) d'un polynôme réel, soit dans tout ℝ, soit dans un intervalle donné. Le théorème de Sturm vous indique qu'une séquence de polynômes qui remplit un petit nombre d'exigences peut être utilisée pour compter le nombre de racines réelles d'un polynôme avec des coefficients réels.

Ensuite, tout ce que vous avez à faire est de construire une telle séquence (ce qui n'est pas très difficile, mais nécessite des cas limites et la gestion du cas des polynômes non séparables), et Bob est votre oncle.

Étonnamment, peu de gens connaissent ce résultat, bien qu'il soit assez ancien (1829). Il est utilisé dans de nombreux systèmes d'algèbre informatique, mais tous les professeurs de mathématiques de mon université à qui j'ai demandé, soit ne connaissaient pas du tout le théorème de Sturm, soit ils ne le connaissaient que de nom et cela avait quelque chose à voir avec les racines des polynômes.

La plupart des gens sont assez surpris lorsque vous leur dites que quelque chose comme le comptage exact des racines est aussi simple et ne nécessite aucune approximation, étant donné que trouver des racines est beaucoup plus difficile. (N'oubliez pas que pour les polynômes de degré ≥ 5, il n'existe même pas de formule «appropriée» pour les racines)

Théorème: chaque graphe planaire a un sommet de degré au plus 5.

Problème: Concevoir une représentation des graphes planaires où l'on peut vérifier si ( u , v ) est une arête en temps O ( 1 ) .$O(n)$$(u, v)$$O(1)$

Nous pouvons supprimer le sommet de degré au plus 5 et l'ajouter à une liste en tant que clé et ses voisins en tant que valeurs. Le graphique restant est également plan et a un sommet de degré au plus 5. Ainsi, l'espace consommé est au plus de . Nous pouvons vérifier si u est dans la liste d'adjacence de v ; sinon, nous pouvons vérifier si v est dans la liste d'adjacence de u . Cela prend au plus 10 étapes.$5n$$u$$v$$v$$u$$10$

Je pense que l'affiche pour cette catégorie, du moins en ce qui concerne l'assymétrie de difficulté, est le problème suivant:

Étant donné un graphe planaire , G 4 peut-il être coloré?$G$$G$

Le théorème des quatre couleurs simplifie l'algorithme return true.

La question de savoir si un polynôme réel (multivarié) peut être exprimé sous la forme d'une somme de carrés de polynômes réels peut être résolue par réduction à une programmation semi-définie. Besoin de connaître SDP et que SDP peut être résolu efficacement.$p$

Autre exemple: étant donné un graphe non orienté, a-t-il une coupe minimale dont toutes les arêtes sont disjointes? Si oui, trouvez-en un.

À première vue, cela peut sembler difficile. Cela devient facile, cependant, si vous connaissez le résultat qu'un graphe -vertex non dirigé peut avoir au plus n ( n - 1 ) / 2 coupes minimales, et elles peuvent toutes être répertoriées en temps polynomial.$n$$n(n-1)/2$

Elle peut être étendue à des coupes presque minimales, qui sont plus grandes que la coupe minimale, mais au plus par un facteur constant. Leur nombre est toujours délimité par un polynôme.

(Je n'ai pas cherché de référence, je me souviens que ces résultats sont dus à D. Karger.)

Problème: Satifsibility d'une formule MSO (logique monadique du second ordre) sur des mots finis.

Théorème: MSO équivaut à des automates finis sur des mots finis.

Ce qui précède peut être élevé en mots infinis, arbres finis, arbres infinis.

Un exemple un peu plus compliqué: la factorisation matricielle non négative , lorsque le rang non négatif est constant.

$A \in M_{m \times n}$$U \in M_{m \times k}$$V \in M_{k \times n}$$A = UV$$A$

$O(r^2)$$r$

$(mn)^{O(r^2)}$$U$$V$$(mn)^{o(r)}$

Décisionnel Diffie Hellman

$(g, g^a, g^b, g^c)$$g$$\mathbb{G}$$g^c = g^{ab}$

Selon les hypothèses standard de dureté d'un problème de log discret, ce problème peut également sembler difficile.

$e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$

Plus d'informations à ce sujet peuvent être lues sur Le problème décisionnel diffie-hellman , Boneh'98 ou une recherche google sur les couplages

(Trivialement) l'existence d'un équilibre de Nash dans un jeu fini, un nombre pair de chemins hamiltoniens dans un graphique cubique, divers types de points fixes, des comparaisons décemment équilibrées dans des ordres partiels et de nombreux autres problèmes de PPAD.

$((V, E), s, t)$$E' \subset E$$s$$t$$(V, E')$$E'$

$s$$t$$(V, E)$$s$$t$

Voici un autre exemple: étant donné un graphe simple non orienté, décidez s'il a deux circuits sommet-disjoints.

$\leq 2$$\geq 3$

$\geq 3$$K_5$$K_{3,n-3}$

Puisqu'il est facile de vérifier si un graphe est l'un des graphes autorisés par le théorème, cela nous fournit un algorithme polynomial pour le problème de décision.

Notes: (1) La preuve du théorème n'est pas du tout facile. (2) Une fois que nous avons décidé que deux circuits disjoints existent, il semble moins clair comment résoudre le problème de recherche associé , c'est-à-dire comment trouver réellement de tels circuits. Le théorème ne donne pas de conseils directs à cela.

exemples moins complexes: il existe des propriétés de type théorème qui montrent que les algorithmes gourmands pour certains problèmes sont optimaux. ce n'est pas si évident pour les non-initiés qu'un arbre couvrant minimum peut être trouvé par un algorithme gourmand. conceptuellement quelque peu similaire est l'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphique. en fait, dans les deux cas, les "théorèmes" associés sont presque les mêmes que les algorithmes.

Trouvez la séquence des nombres de Fibonacci qui sont le produit d'autres nombres de Fibonacci. Par exemple, le nombre de Fibonacci 8 est dans la séquence parce que 8 = 2 * 2 * 2, et 2 est un nombre de Fibonacci qui n'est pas égal à 8. Le nombre de Fibonacci 144 est dans la séquence parce que 144 = 3 * 3 * 2 * 2 * 2 * 2, et 2 et 3 sont des nombres de Fibonacci qui ne sont pas égaux à 144.

Le théorème de Carmichael implique que 8 et 144 sont les seuls termes de cette séquence.