Conséquences d'un algorithme temporel quasi-polynomial pour le problème de l'isomorphisme de graphe

40

Le problème de l’isomorphisme graphique (IG) est sans doute le candidat le mieux connu pour un problème NP-intermédiaire . L'algorithme le plus connu est l'algorithme sous-exponentiel avec la durée d'exécution . On sait que GI n’est pas complet sauf si la hiérarchie polynomiale s’effondre.NP2O(nlogn)NP

Quelles seraient les conséquences théoriques de la complexité d'un algorithme temporel quasi polynomial pour le problème de l'isomorphisme de graphes?
Un algorithme temporel quasi-polynomial pour GI réfuterait-il des conjectures célèbres de la théorie de la complexité?


D'autres problèmes similaires, tels que le problème de jeu dominant minimal dans les tournois, le problème d'isomorphisme de groupe et le problème d'isomorphisme de tournoi ont des algorithmes de temps quasi-polynomial ( QP ). Les deux derniers problèmes sont réductibles au temps polynomial en GI.

Pouvons-nous efficacement réduire le problème de l'ensemble de dominants minimaux dans les tournois à GI?
Existe-t-il une hypothèse selon laquelle GI serait difficile pour QP?

Mise à jour (2015-12-14) : Babai a publié un avant-projet de document sur arXiv pour son algorithme quasi-polynomial pour GI.

Mise à jour (2017-01-04) : Babai a rétracté l'affirmation selon laquelle l'algorithme est en temps quasi-polynomial. Selon la nouvelle analyse, l'algorithme est en temps subexponentiel. qui est à l'intérieur de .2 n o ( 1 )expexp(O~(lgn))2no(1)

Mise à jour (2017-01-09) : Babai a rétabli la revendication de délai quasi-polynomial, remplaçant la procédure incriminée par une procédure plus efficace.

Mohammad Al-Turkistany
la source
6
Je pense que beaucoup de gens pensent qu’il a un algorithme de temps polynomial, et un tel algorithme n’a aucune conséquence théorique sur la complexité.
Huck Bennett
7
Ce n’est pas tout à fait ce que vous demandez, mais c’est le meilleur que je connaisse: l’isomorphisme de groupe a un algorithme naturel et facile quasi-polynomial, mais il n’existe manifestement aucune réduction de de GI à GroupIso: eccc.hpi-web.de/report/2010/117 . Une question formellement plus facile que ce que vous demandez, mais toujours ouverte, est de prouver qu’il n’ya pas de réduction du temps multiple entre IG et GroupIso. AC0
Joshua Grochow
14
Après deux ans, je pense que nous avons une réponse. Laszlo Babai a prouvé que GI avait un algorithme temporel quasi polynomial. Source: lucatrevisan.wordpress.com/2015/11/03/…
user3415207
8
@ user3415207 Babai a rétracté l'allégation de runtime quasi polynomiale . Apparemment, il y avait une erreur dans l'analyse.
Raphaël
6
@Raphael ... et Babai a rétabli sa revendication (même lien que le vôtre).
Danny

Réponses:

5

Autant que je sache, si vous vous interrogez simplement sur les conséquences du simple fait (en tant que boîte noire) que GI est dans QP, je pense que la réponse est très petite. La seule chose à laquelle je puisse penser, qui n’est pas un théorème mais une conséquence pour les directions de recherche, est celle de l’ isomorphisme de groupe . Puisque GroupIso se réduit à IG et que nous ne savons même pas si GroupIso est dans P, placer GroupIso dans P peut être considéré comme un obstacle important à la transformation de GI en P (si vous pensez que ce dernier pourrait être le cas).

Cependant, comme l’algorithme trivial pour GroupIso est , à l’époque où la complexité de GI était en hausse à , nous avons eu une longue Il reste encore beaucoup à faire pour améliorer la complexité de l’IG avant que GroupIso ne devienne un obstacle immédiatement pertinent à l’ intégration de l’ IG dans un point P. Cependant, si l’IG est dans QP, GroupIso devient alors un obstacle beaucoup plus pertinent à de nouvelles améliorations de l’IG. (Bien entendu, l'exposant de l'exposant dans le quasi-polynôme est toujours un écart potentiellement pertinent, mais l'écart devient beaucoup plus petit lorsque GI est dans QP.) 2 ~ O ( nlogn+O(1)2O~(n)

Joshua Grochow
la source
Il semble que nous ne soyons pas en mesure d’améliorer la borne supérieure beaucoup plus faible du test de l’isomorphisme des plans projectifs ( ). Voir cstheory.stackexchange.com/questions/34773/…nO(loglogn)
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Oui, mais c'est le même argument que je retiens: si GI est "presque" impuissant, alors ProjPlaneIso est très loin d'être un obstacle à l'intégration de GI dans P. Une fois que GI est dans le temps pour certains , alors ProjPlaneIso deviendrait un obstacle important. Donc, pour le moment, il semblerait que GroupIso soit l'obstacle le plus immédiat - peut-être qu'un jour ProjPlaneIso le sera aussi ... cnO(loglogn)cc
Joshua Grochow
@JoshuaGrochow Seriez-vous d'accord avec moi pour dire que l'approche adoptée par François Le Gall et David J. Rosenbaum dans On the Group et Color Isomorphism Problems est logique? Ou du moins qu'ils traitent certaines questions qui pourraient se poser après avoir acquis une compréhension de base du résultat de László Babai?
Thomas Klimpel
@ThomasKlimpel: Je conviens que leur article a du sens, même si je ne vois pas encore comment tirer parti de leurs idées (malgré la compréhension de la plupart des preuves de Babai).
Joshua Grochow
Ne croyez-vous pas que l'IG dans QP conduirait finalement à placer l'IG dans une classe de non-déterminisme limitée telle que ? βkP
Mohammad Al-Turkistany le
2

Σ

Emil Jeřábek soutient Monica
la source
0

Quelles seraient les conséquences théoriques de la complexité d'un algorithme temporel quasi polynomial pour le problème de l'isomorphisme de graphes?

Plus ou moins similaires aux conséquences de l'algorithme temporel polynomial déterministe pour le test de primalité, l'algorithme temporel polynomial déterministe pour la programmation linéaire, et dans l'autre cas, des algorithmes pratiquement efficaces (randomisés) (avec des exemples pathologiques rares où l'algorithme devenait inefficace) étaient connus et utilisé depuis longtemps. Cela confirme l'hypothèse selon laquelle l'efficacité pratique est un bon indicateur de l'existence d'algorithmes théoriques déterministes surmontant les problèmes des exemples pathologiques rares.

Un algorithme temporel quasi-polynomial pour GI réfuterait-il des conjectures célèbres de la théorie de la complexité?

Non, les conjectures vont plutôt au site opposé, à savoir que GI est en P. Puisque GI est en NP, il ne sera pas possible de réfuter ce type de conjecture de si tôt.

Pouvons-nous efficacement réduire le problème de l'ensemble de dominants minimaux dans les tournois à GI?

L'ensemble dominant minimal n'est pas un problème d'isomorphisme, il n'y a donc aucune raison pour qu'il soit supposé être réductible à IG.

Existe-t-il une hypothèse selon laquelle GI serait difficile pour QP?

Nous ne savons même pas comment réduire le problème d'isomorphisme de chaîne à GI, et il s'agit au moins d'un problème d'isomorphisme. La preuve de Babai a montré que l'isomorphisme des cordes était dans QP, alors ... Et qu'est-ce qui est difficile pour QP même supposé vouloir dire? Dur sous les réductions de temps polynomiales?


Depuis l'introduction de Sur le groupe et les problèmes d'isomorphisme de couleur de François Le Gall et David J. Rosenbaum

La complexité des problèmes de test d’isomorphisme est digne d’être étudiée à la fois parce qu’il s’agit de questions de calcul fondamentales et aussi parce que beaucoup d’entre eux ne sont pas connus pour être dans P, mais semblent néanmoins être plus faciles que les problèmes NP-complets. Le plus étudié de ces problèmes est le problème de l’isomorphisme des graphes.

GIGrIsont définis (dans l'article ci-dessus, mais les auteurs se demandent à juste titre pourquoi personne ne l'a fait auparavant), ce qui ajoute les pièces manquantes au problème de l'isomorphisme des chaînes. (Et le problème d'isomorphisme de couleur est simplement un nom différent pour le problème d'isomorphisme de chaîne. Le problème d'automorphisme de couleur de nom remonte aux papiers initiaux de Babai et Luks, l'isomorphisme de chaîne de nom apparaît plus tard dans leur article sur l'étiquetage canonique.)

GI


Edit: Cette réponse a été donnée dans le contexte de la rétractation du résultat de Babai, avant qu'il n'annonce un correctif. Cela suggère que la légère généralisation du problème d'isomorphisme de graphe suggérée par le problème d'isomorphisme de chaîne est le problème vraiment important. On s’attend implicitement à ce que tout algorithme raisonnable pour le problème de l’isomorphisme des graphes conduise à un algorithme similaire pour le problème de l’isomorphisme généralisé des graphes. Le problème généralisé est le temps polynomial équivalent au problème stabilisateur d'ensemble , au problème d'intersection de groupe , au problème d'intersection de coset, au problème de transporteur d'ensemble , ... L'idée derrière cette attente est que le problème généralisé se produira dans la partie récursivede tout algorithme raisonnable, il doit donc être traité de toute façon. (Et il est fort possible que le problème généralisé soit le temps polynomial équivalent à l'isomorphisme de graphe.)

Les commentaires de Joshua Grochow indiquent maintenant que je n'ai pas réussi à expliquer l'importance conceptuelle des pièces manquantes du problème de l'isomorphisme des cordes. Pour les structures infinies, il peut être plus facile de comprendre qu'un isomorphisme valide doit non seulement préserver la structure donnée, mais également appartenir à une catégorie appropriée de fonctions (par exemple, la catégorie des fonctions continues). Pour les structures finies, le phénomène analogue se produit principalement pour les structures de quotient, où la catégorie de fonctions appropriée doit être compatible avec les quotients donnés. Le truc Johnson est un exemple typique de tels quotients, par exemple, la logique de partition fonctionne sur les deux sous-ensembles d'éléments d'un ensemble de base. Notez également que la restriction de la catégorie autorisée pour les isomorphismes facilite souvent le problème du test d’isomorphisme,

Le problème des généralisations du problème d’isomorphisme de graphe est de savoir où s’arrêter. Pourquoi ne pas généraliser jusqu'à englober le problème de l'isomorphisme de groupe de permutation? Cette question est vraiment difficile, car de nombreux résultats non triviaux pour l'isomorphisme des graphes se répercuteront probablement également sur l'isomorphisme du groupe de permutation. Mais ici, il semble plus raisonnable de traiter la théorie des groupes de permutation informatique comme un sujet à part entière, même si elle a effectivement un lien étroit avec le problème de l’isomorphisme des graphes.

Thomas Klimpel
la source
1
Sn
1
@JoshuaGrochow Pour color iso, les couleurs ne sont que des nombres arbitraires (wlog limité à [n]). Pour chaîne iso, les chaînes sont données sur un alphabet fini fixe. Je pensais que c'était un alphabet binaire, mais je me suis mal souvenu de cela. Je viens de me rappeler que j'avais au départ été confus si l'iso couleur était simplement un nom différent pour l'iso chaîne. Alors, quand j'ai décidé de lire ce journal après que Laszlo eut rétracté sa revendication, cela m'a semblé être une différence. Peut-être que c'est vraiment une différence, parce que "sur un alphabet fini" communique "corrigez votre alphabet fini préféré, cela ne fera aucune différence". Ce qui est vrai.
Thomas Klimpel
1
logn[n]
1
@JoshuaGrochow C'est exactement ce que je voulais dire par cela ne fera aucune différence ". Ce qui est vrai. J'essayais maintenant de répondre à votre commentaire" L'isomorphisme de chaîne / l'isomorphisme de couleur ne tombe pas dans cette classe ". J'ai aimé apprendre quelques leçons de Andreas Blass et Yuri Gurevich sont sur le chemin, ils essaient également de se concentrer sur des points conceptuels. Je suis heureux que Babai ait corrigé son algorithme maintenant, de sorte que je ne ressente aucune obligation (ni pression) de rechercher si l'isomorphisme des graphes et l'isomorphisme des chaînes sont équivalents en temps polynomial. (Quel est le contexte pour lequel j’ai écrit cette réponse)
Thomas Klimpel le
Je ne comprends pas pourquoi vous comparez les progrès en matière de GI avec les résultats de la dérandomisation.
Sasho Nikolov