«Petit» isomorphisme graphique

En réfléchissant à la complexité du test de l'isomorphisme des graphes asymétriques (voir ma question connexe sur la théorie), une question complémentaire m'est venue à l'esprit.

Supposons que nous ayons une machine de Turing à temps polynomial qui en entrée génère un graphe avec nœuds.1 n G M , n$M$$1^n$$G_{M,n}$$n$

Nous pouvons définir le problème :$\Pi_M$

(GI "minuscule"): Étant donné un graphique , est-il isomorphe à ?G G M , | V $G=(V,E)$$G$$G_{M,|V|}$

En d'autres termes, nous devons comparer un graphe donné avec un graphe "de référence" de même taille généré par une machine de Turing temps polynomial fixe .$M$

Pour tous les temps polynomiale machines de Turing , nous avons , et pour beaucoup d'entre eux nous avons . Mais est-ce vrai pour tout ? Le problème est-il connu?Π M ∈ N P Π M ∈ P $M$$\Pi_M \in NP$$\Pi_M \in P$
$M$

À première vue, je pensais que chaque devrait être beaucoup plus facile que , car pour chaque il n'y a qu'un seul graphique "de référence" de cette taille et peut-être que les symétries / asymétries des graphiques générés par peuvent être exploitées et un un testeur d'isomorphisme ad hoc peut être construit ... mais ce n'est pas vrai: peut contenir une sorte de machine de Turing universelle temporisée polynomiale qui utilise l'entrée (unaire) pour générer des graphiques de référence complètement différents (dans la structure) comme augmente. G I n M M 1 n$\Pi_M$$GI$$n$$M$$M$$1^n$$n$

[Il s'agit plus de quelques commentaires prolongés que d'une réponse.]

1) Si , alors il n'y a pas de limite de polynôme fixe sur la complexité temporelle de tous les Π M , même pour M qui ne prend que du temps, disons n 3 : Si pour tout le temps - n 3 M , Π M ∈ D T I M E ( n k ) , alors ce qui suit est un algorithme poly-temps pour GI. En entrée ( G , H ) , construire une machine de Turing M G avec une horloge qui assure que M $GI \notin \mathsf{P}$$\Pi_{M}$$M$$n^3$$n^3$ $M$$\Pi_{M} \in \mathsf{DTIME}(n^k)$$(G, H)$$M_{G}$$M_{G}$ne court jamais plus de étapes sur des entrées de taille n , et telles que M G ( 1 | V ( G ) | ) = G , puis résolvent Π M G ( H ) dans le temps O ( n k ) .$n^3$$n$$M_{G}(1^{|V(G)|}) = G$$\Pi_{M_G}(H)$$O(n^k)$

2) Étant donné que pour tout , Π M n'est pas plus difficile que GI, on pourrait penser que le meilleur résultat du type " Π M ne semble pas être en P " que l'on pourrait espérer est un résultat d'exhaustivité GI. Cependant, il me semble peu probable que n'importe quel Π M soit GI-complet, pour au moins les raisons suivantes:$M$$\Pi_{M}$$\Pi_M$$\mathsf{P}$$\Pi_M$

• Tous les résultats d'exhaustivité de l'IG que je connais concernent des classes de graphiques plutôt importantes, plutôt que d'avoir un seul graphique de chaque taille. Même si vous supprimez entièrement l'exigence d'efficacité, je ne connais aucune liste de graphes telle que | V ( G n ) | = n (ou même p o l y ( n ) ) de sorte que le test de l'isomorphisme en G n est GI-complet.$G_1, G_2, \dotsc$$|V(G_n)| = n$$poly(n)$$G_n$

• Sur une note connexe, la plupart (tous?) Des résultats d'exhaustivité de l'IG ne sont pas simplement des réductions de plusieurs, mais ont la forme suivante: il existe une fonction telle que, étant donné une instance ( G , H ) de GI, ( f ( G ) , f ( H ) ) est une instance de l'autre problème GI-complet. (Ce ne sont que des morphismes poly-temps de relations d'équivalence, ou ce que Fortnow et moi avons appelé «réductions de noyau».) Nous pouvons facilement montrer sans condition qu'il n'y a pas une telle réduction de GI à un Π M (même si vous modifiez la définition pour autoriser $f$$(G,H)$$(f(G), f(H))$$\Pi_M$$M$pour produire plusieurs graphiques). Astuce: Obtenez une contradiction en montrant que tout doit avoir son image complètement contenue dans { G M , n } n ≥ 0 .$f$$\{G_{M,n}\}_{n \geq 0}$

3) Même si l'on pouvait construire sur la base d'une MT universelle comme suggéré dans la question, on peut peut-être encore construire un testeur efficace, mais pas efficacement. Autrement dit, peut-être pour chaque M , Π M est dans P / p o l y ?$M$$M$$\Pi_{M}$$\mathsf{P/poly}$

Je n'ai pas de réponse à votre question mais propose d'envisager une version plus restreinte de pour laquelle nous pouvons montrer qu'elle se situe en P.$\Pi_M$

Considérons uniquement les familles de graphes telles que le nombre d'arêtes croît logarithmiquement. Je vais formaliser cela en reformulant la formulation de votre problème, également pour voir si je l'ai bien compris.

Un graphe non orienté à n bords peut être décrit par un n 2 - $G$$n$ longues chaînes de bits, simplement concaténer les entrées de la matrice d'adjacence deGdans le triangle supérieur. Il y a donc2 n 2 - $\frac{n^2-n}{2}$$G$ graphes possibles surnsommets. Il s'ensuit que toute fonctionf:N→Ntelle que0≤f(n)<2n2-$2^{\frac{n^2-n}{2}}$$n$$f : \mathbb{N} \rightarrow \mathbb{N}$ pour toutndécrit une famille de graphiques. Pour toute fonctionfefficacement calculable,nous définissonsΠfcomme G∈Π$0 \leq f(n) < 2^{\frac{n^2-n}{2}}$$n$$f$$\Pi_f$

Pour un nombre naturel soit b 1 ( x ) le nombre de 1 dans sa représentation binaire. Maintenant, considérons que Π f pour les fonctions efficacement calculables f pour lesquelles il estime que b 1 ( f ( n ) ) ∈ O ( log n ) qui est familles de graphes pour lesquels le nombre d'arêtes ne pousse que logarithmiquement, comme indiqué ci - dessus .$x$$b_1(x)$$\Pi_f$$f$

Nous montrons que pour cette classe de fonctions est en P.$\Pi_f$

$f$$G$$n$$f(n)$$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$$n$$\mathcal{O}(\log n)$$n$parce que nous pouvons essayer toutes les permutations. Ainsi, en utilisant un algorithme gourmand pour attribuer à chaque MCC du graphe d'entrée un MCC dans le graphe de référence, nous pouvons déterminer si les deux graphes sont isomorphes.