Le problème d'isomorphisme du graphe a-t-il été résolu?

13

La page de problème d'isomorphisme de Wikipedia semble indiquer que non, elle n'a pas été résolue. Cependant, un de mes amis a souligné un algorithme de temps polynomial pour l'isomorphisme graphique . Je ne suis pas assez sophistiqué pour suivre le raisonnement du document.

J'ai ma propre tentative très approximative d'un algorithme de temps polynomial sans rien de comparable, mais j'aimerais savoir si ce problème a été résolu avec succès avant de continuer.

Alors, le problème d'isomorphisme du graphe est-il résolu?

complexity-theory reference-request time-complexity graph-isomorphism Tyler Spaeth
la source
1
question valable. par rapport à l'examen par les pairs, il serait préférable que les répondants / réponses signalent effectivement des erreurs spécifiques dans le document plutôt que des généralités. certes, cependant, voici ce que les scientifiques professionnels pensent de ces types d'efforts. arxiv est plein de papiers erronés, beaucoup sur P vs NP mais beaucoup d'autres problèmes semi-fameux attirent les efforts amateurs, par exemple aussi la conjecture Collatz, les nombres premiers jumeaux, la conjecture Goldbach, etc.
vzn
7
@vzn Je ne pense pas qu'il soit inutile de perdre notre temps à lire des articles qui sont presque sûrement incorrects et n'apportent aucun éclairage nouveau sur le problème.
Yuval Filmus
2
@vzn Je ne comprends pas votre plainte. La réponse de DW (affiché une heure avant votre commentaire) des liens vers un commentaire qui fait le point sur une erreur spécifique dans le document ArXiv en discussion.
David Richerby
2
@vzn Le papier ArXiv contient une erreur. Il n'a pas été révisé pour corriger cette erreur. Il n'est plus nécessaire de procéder à un examen par les pairs. Je ne sais pas ce que vous dites est de seconde main: un contre-exemple est un contre-exemple, qu'il vous soit communiqué par son découvreur ou par le trafiquant de drogue qui traîne derrière cette barre minable sur l'autoroute.
David Richerby
1
@vzn Vraisemblablement, il n'a pas été révisé car l'auteur n'a pas pu corriger l'erreur. Notez qu'ArXiv n'autorise pas le retrait des manuscrits, même s'ils s'avèrent incorrects.
David Richerby

Réponses:

23

Non. Ce document semble être imparfait. La faille a été expliquée dans un commentaire de Tracy Hall sur MathOverflow . Un commentaire de suivi affirme que l'auteur a réalisé plus tard qu'il y avait une faille dans son algorithme.

Comme l'explique Yuval, il n'est pas rare de voir des tentatives d'amateurs résoudre ces problèmes; ils ont tendance à être défectueux. En ce qui concerne les résultats sur les problèmes ouverts connus (par exemple, P vs NP, isomorphisme graphique, etc.), je recommande de consulter la littérature publiée dans des conférences et des revues à comité de lecture réputées - l'examen par les pairs n'est pas parfait, mais les articles évalués par les pairs ont une probabilité beaucoup plus élevée d'avoir raison.

DW
la source
17

Non, le problème d'isomorphisme du graphe n'a pas été résolu. Le document auquel vous vous connectez date de 2007-2008 et n'a pas été accepté par la communauté scientifique au sens large. (Si cela avait été le cas, je l'aurais su.)

L'isomorphisme graphique, comme beaucoup d'autres problèmes connus, attire de nombreuses tentatives d'amateurs. Ils ont presque toujours tort. Je déconseille d'essayer de résoudre ce problème sans devenir d'abord compétent en mathématiques de niveau recherche.

Yuval Filmus
la source
2
une autre façon de traiter ces types de réclamations par des experts est l'impossibilité ou les résultats d'obstacles. alors une réfutation plus informative se présente sous la forme "l'article utilise un type d'argument [x] pour essayer de résoudre le problème d'isomorphisme, mais il est connu d'après les recherches [a, b, c] qu'il existe une barrière spécifique à ce type d'approche, et le document semble ignorer cet obstacle ou révéler spécifiquement comment il est surmonté. " il existe des résultats connus à ce sujet pour le problème d'isomorphisme et d'autres problèmes clés, par exemple P vs NP.
vzn
1
Tenter des problèmes non résolus comme celui-ci (et échouer ..) peut être un exercice d'apprentissage très fructueux, si l'on arrive avec la bonne mentalité.
Nick Alger
cependant, certains chicanent : les preuves / allégations ont une validité dans une certaine mesure indépendante de «l'acceptation par la communauté scientifique au sens large» et de leur connaissance par des individus particuliers. Par exemple, lorsqu'une preuve correcte est introduite pour la première fois, elle n'est pas "acceptée" immédiatement / instantanément par une personne autre que l'auteur. un soutien supplémentaire à cette dynamique se trouve dans l'histoire des mathématiques. & parfois de longues périodes peuvent s'écouler entre l'introduction de revendications / assertions et l'acceptation, par exemple dans le cas de Galois, Ramanujan, etc.
vzn
8

Je serais très douteux que ce soit le cas (au sens de la preuve de l'existence d'un algorithme polynomial temporel). Bien qu'il ne soit pas impossible que le papier soit correct, il existe un certain nombre de signes d'avertissement:

  1. L'auteur n'a pas publié le résultat dans un lieu évalué par les pairs (même après 7 ans).
  2. L'auteur ne semble avoir rien publié d'autre, nulle part.
  3. L'article présente les algorithmes, mais la revendication de la justesse est un argument informel de la main sur la complexité.
  4. Pour un problème qui a résisté aux tentatives de certaines personnes très intelligentes, les calculs dans le document sont trop simples.
  5. L'auteur ne semble pas être affilié à une institution académique. La nouvelle version du document clarifie cela.

Encore une fois, sans que quelqu'un n'identifie un défaut dans le papier, ce ne sont pas des signes infaillibles. L'auteur a peut-être eu un aperçu unique et est ensuite passé à une vie complètement différente, mais le poids de la probabilité est contre - les affirmations extraordinaires nécessitent des preuves extraordinaires.

Pour approfondir (4) les informations récentes, László Babai a récemment revendiqué une amélioration majeure de l'algorithme d'isomorphisme de graphe connu (pas encore de préimpression, mais un commentaire de fonctionnement décent sur sa conférence publique peut être trouvé ici ), donnant un algorithme de temps pseudo-polynomial. Babai et ses collègues sont certainement des gens très intelligents, et les mathématiques utilisées pour obtenir ce résultat sont difficiles, profondes et couvrent la théorie des graphes et la théorie des groupes. Compte tenu du poids de la probabilité, il s'agit du niveau attendu pour une avancée significative sur un problème comme celui-ci.

Luke Mathieson
la source
3
Les points 1 à 4 sont solides, mais 5 est beaucoup plus circonstanciel.
David Richerby
(5) n'est pas correct. l'institution (apparemment) est l' Université technique de Berlin et est en partie financée par l'État. (1) soutenu par ce lien / crawler papier. l'article est cité sur la page des revendications de Woeginger .
vzn
3
Babai a rétracté la revendication de l'exécution quasi-polynomiale . Apparemment, il y avait une erreur dans l'analyse.
Raphael
rétablissement de la revendication de quasi
polynôme
3

Laszlo Babai a affirmé avoir trouvé une solution quasi-polynomiale pour le problème d'isomorphisme des graphes au 11 novembre 2015.

... et a rétracté la réclamation hier (01/04/2017):

Source: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

bharv14
la source
D'après le lien que vous avez fourni: Babai n'a pas encore publié de préimpression, et quand je lui ai demandé, il a dit "bientôt, bientôt". Jusque là.
scaaahu
La question ne définit pas ce que cela signifierait pour que le problème d'isomorphisme du graphe soit considéré comme résolu, mais l'interprétation la plus probable est: que quelqu'un a trouvé un algorithme de temps polynomial pour cela, ou a donné la preuve qu'aucun tel algorithme de temps polynomial n'existe . Selon cette interprétation, cette réponse ne répond pas à la question.
DW
4
Babai a rétracté la revendication de l'exécution quasi-polynomiale . Apparemment, il y avait une erreur dans l'analyse.
Raphael
rétablissement de la revendication de quasi
polynôme