Quel est l'état du résultat d'isomorphisme du graphique de Babai?

23

Cela fait plus d'un an depuis sa rétractation et sa correction de janvier 2017. Y a-t-il des nouvelles?
Sinon, est-ce normal que la validation prenne autant de temps? Je m'attendrais à ce qu'il retienne beaucoup d'attention Quelqu'un de remarquable a-t-il parlé pour soutenir / douter du résultat quasi polynomial?

cc.complexity-theory graph-isomorphism proofs Meir Maor
la source
6
La correction (et donc le résultat quasi polynomial) a été immédiatement soutenue par Harald Andrés Helfgott. Son exposé ( arxiv.org/abs/1701.04372 ) et sa traduction ( arxiv.org/abs/1710.04574 ) sont tout le support nécessaire pour les résultats quasi polynomiaux (tant qu'aucun autre trou ou erreur n'est trouvé). Il n'y a pas de nouvelles à attendre.
Thomas Klimpel
ont-ils été publiés quelque part? (pas arxiv)
Meir Maor
5
Il est écrit "À paraître à Astérisque. Fascicule n ° 1125 du séminaire Bourbaki (69e année, 2016-2017)" sur arXiv. Il n'est pas encore paru, ( smf4.emath.fr/Publications/Asterisque/2017 ) répertorie "Séminaire Bourbaki, volume 2015/2016", et ( smf4.emath.fr/Publications/Asterisque ) ne répertorie encore rien de 2018.
Thomas Klimpel
10
Il est tout à fait normal qu'un article de mathématiques prenne plus d'un an, voire plus de deux ans pour être publié.
Sasho Nikolov
3
D'un autre côté, la publication d'un article ne signifie pas que les résultats sont corrects. Il existe de nombreux cas de résultats retirés après avoir été publiés dans des revues. Par exemple, sciencedirect.com/science/article/pii/…
Mohammad Al-Turkistany

Réponses:

20

Regroupement des commentaires de Thomas Klimpel, Sasho Nikolov et Mohammad Al-Turkistany en une réponse communautaire:

La correction (et donc le résultat quasi polynomial) a été immédiatement soutenue par Harald Andrés Helfgott. Son exposé ( https://arxiv.org/abs/1701.04372 ) et sa traduction ( https://arxiv.org/abs/1710.04574 ) sont tous les supports nécessaires aux résultats quasi polynomiaux. L'exposition d'Helfgott a été publiée sous le titre Exposé 1125 dans Astérisque 407 (2019), Séminaire Bourbaki 2016/2017, pp. 135-182.

Il n'y a actuellement aucun problème connu avec la preuve de Babai, et elle a fait l'objet d'un examen approfondi par les pairs. Cela dit, même les articles publiés par des pairs ont par la suite été retirés comme étant incorrects.

Le soutien de Harald Andrés Helfgott ainsi que l'absence d'autres problèmes devraient être suffisants pour que nous acceptions que l'isomorphisme des graphes est en effet résoluble en temps quasi polynomial.

Meir Maor
la source
4
Dans le cas où ce n'est pas clair, la chose qui "doit apparaître" dans le séminaire Bourbaki est l'exposition d'Helfgott, pas l'article de Babai.
Sasho Nikolov
Remarque J'ai délibérément fait de cette réponse un wiki communautaire, non seulement pour ne pas prendre le crédit, mais toute personne, y compris vous, peut facilement la modifier pour apporter des améliorations / clarifications.
Meir Maor