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

28

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 dn,k,l,dnkld

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 dn,k,l,dnkld

  • 0kld<n/2 ,
  • 12d+2nkl=d<n1
  • k=l=d=n1.

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?

Andras Farago
la source
1
Je ne suis pas sûr de bien comprendre vos questions. L'exemple que vous donnez est un problème non trivial pour lequel Bollobas a donné un algorithme (ce qui implique une caractérisation). Donc, mon impression avec votre exemple est que tout algorithme non trivial sera une réponse ...
Bruno
3
Primalité et théorème AKS.
Lamine
@Bruno: Ce que je veux dire, c'est que la tâche algorithmique devient beaucoup plus facile si vous connaissez un théorème, qui n'est pas bien connu, donc on peut ne jamais en avoir entendu parler. L'exemple présenté n'est pas parfait dans le sens où ici le théorème n'aide pas seulement, il résout en fait le problème. Ce que je recherche vraiment, c'est quand un théorème aide, fournit un raccourci utile, mais ne résout pas complètement le problème en soi.
Andras Farago
3
Wiki communautaire?
Joshua Grochow
1
Théorème de Robertson – Seymour, également des conjectures qui facilitent la recherche déterministe des nombres premiers.
Kaveh

Réponses:

31

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é).

Joshua Grochow
la source
3
Ceci est un excellent exemple! BTW les commentaires de cette réponse affirment que, dans un certain sens, ce théorème est à peu près aussi difficile que la classification: mathoverflow.net/a/59216/35733
Sasho Nikolov
32

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.GG

Sasho Nikolov
la source
20

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 .xym,nxm=yn

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

Pratik Deoghare
la source
9

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)

Manuel Eberl
la source
9

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.5nuvvu10

Pratik Deoghare
la source
5
Avec un peu plus de soin, vous pouvez réduire la taille de la liste stockée à chaque sommet à 3 et le nombre d'étapes pour vérifier la contiguïté à 6. Voir: Orientations planaires avec un faible degré de sortie et compactage des matrices de contiguïté. M. Chrobak et D. Eppstein. Théor. Comp. Sci. 86 (2): 243-266, 1991. ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf
David Eppstein
7

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é?GG

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

Jonas Kölker
la source
6

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

Chandra Chekuri
la source
5

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.nn(n1)/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.)

Andras Farago
la source
4

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.

Denis
la source
4

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

AMm×nUMm×kVMk×nA=UVA

O(r2)r

(mn)O(r2)UV(mn)o(r)

zotachidil
la source
4

Décisionnel Diffie Hellman

(g,gune,gb,gc)gggc=guneb

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

e(g,gc)=?e(gune,gb)

e:g×ggT

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

Subhayan
la source
3

(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.

Yonatan N
la source
L'existence de Nash Equilibrium - et de nombreuses autres preuves d'existence qui ont caractérisé PPAD - ne semble pas faciliter la résolution algorithmique de ces problèmes ...
Joshua Grochow
1
Je faisais référence à la version décisionnelle de ces problèmes.
Yonatan N
2

((V,E),s,t)EEst(V,E)E

st(V,E)st

Max
la source
1
On peut dire que l'écoulement est facile si vous savez que LP est facile. Ainsi, deux grands théorèmes (LP en poly temps et maxflow-mincut) nous permettent de calculer des min-coupes.
Chandra Chekuri
@ChandraChekuri, mon sentiment personnel est que cela ne correspond pas tout à fait à la question: le théorème selon lequel le LP est résoluble en polytemps ne nous aide pas à construire un algorithme pour les coupes min. Nous avons besoin de l'algorithme LP réel.
Max
Pas vraiment. Si vous pouvez trouver la valeur de coupe minimale dans un graphique donné de manière efficace, vous pouvez utiliser un tel algorithme pour trouver la coupe réelle elle-même.
Chandra Chekuri
2

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

23

3K5K3,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.

Andras Farago
la source
1

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.

vzn
la source
Je pense que ce sera une meilleure réponse si, par exemple, vous incluez une déclaration de la propriété cut de MST et mentionnez comment cela implique l'exactitude de toute une classe d'algorithmes MST gourmands.
Sasho Nikolov
Propriété de coupe MST répertoriée sur la page wikipedia peut-être pouvez-vous référencer d'autres généralisations non couvertes ici. rappelez-vous que l'interrogateur a demandé des exemples au service de "ceux qui sont en dehors du domaine de la théorie" (d'autres beaux exemples donnés peuvent être trop avancés pour les étrangers)
vzn
TeT-eABeE(UNE,B)
1

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.

Bob Lyons
la source