Quelle est la dureté connue actuelle de l'isomorphisme graphique?

Inspiré par la question de l' affacturage connu pour être P-dur , je me demande quel est l'état similaire actuel des connaissances sur la dureté de l'isomorphisme du graphe. Je suis sûr que l'on ne sait pas actuellement si GI est en P, mais:

quelle est la plus grande classe actuellement connue que l'IG est plus difficile que?

(il n'a pas été répondu à une question similaire )

Pour répondre à certains des commentaires, je veux connaître la ou les classes maximales actuellement connues pour lesquelles GI, le problème est complet. Les algorithmes connus pour GI sont délimités par des fonctions superpolynomiales, et il est membre de NP. Mais on ne sait pas que GI est P-dur. Je voudrais connaître toutes les classes C pour lesquelles il - est connu que c'est C-difficile, et si tout va bien aussi inclusif que possible.

cc.complexity-theory complexity-classes graph-isomorphism Mitch
la source

"il n'a pas été répondu à une question similaire" Vraiment? Je pense que la réponse de Joshua Grochow là-bas répond à la question ici.

Tyson Williams

Regardez la section "Complexity Class GI" ici: en.wikipedia.org/wiki/Graph_isomorphism_problem

Aaron Sterling

@Tyson et quiconque a voté pour son commentaire: Je pense que ce que Mitch dit, c'est que la réponse ne donne que des limites supérieures sur l'isomorphisme graphique, pas la dureté de l'isomorphisme graphique.

Tsuyoshi Ito

Je voudrais ajouter que je ne vois pas cela comme une question en double. La réponse de Josué donne des limites supérieures. Cette question ressemble plus à: "L'IG est-il au moins AC0 difficile?" - oui, d'accord avec @Tsuyoshi.

Aaron Sterling

Pour les graphiques planaires, il est connu pour être complet pour L ... Voir theorie.informatik.uni-ulm.de/Personen/toran/beatcs/…

Joshua Herman

Quelle est la dureté connue actuelle de l'isomorphisme graphique?

Réponses: