Certificat coNP pour l'isomorphisme graphique

29

Il est facile de voir que l' isomorphisme graphique (GI) est en NP. C'est un problème ouvert majeur si l'IG est en coNP. Existe-t-il des candidats potentiels aux propriétés des graphiques qui peuvent être utilisés comme certificats IG de coNP? Des conjectures impliquant ? Quelles sont les implications de G I c o N P ?gjecoNPgjecoNP

Shiva Kintali
la source

Réponses:

21

Si est en c o N P , alors nous avons le résultat: G Je n'est pas N P -complete moins que N P = c o N P = P H . (Actuellement connu: G I n'est pas N P- complet sauf si Σ 2 P = Π 2 P = P H ).gjecoNPgjeNPNP=coNP=PHgjeNPΣ2P=Π2P=PH

Puisque est en c o Un M , évidemment derandomizing c o A M ( lien DOI ) serait mis G I C o N P , mais je ne sais aucune propriété graphique candidat pour mettre G I C o N P autrement. J'attends cependant avec impatience d'autres réponses!gjecoUNEMcoUNEMgjecoNPgjecoNP

Fait intéressant, dans ce document , ils montrent également que le graphique non isomorphisme a des preuves de taille sous - exponentiels - qui est, - à moins que P H = Σ 3 P . Ceci est au moins dirigé dans la direction de projection sous condition que G I c o N P .gjecoNSUBEXPPH=Σ3PgjecoNP

Joshua Grochow
la source
5
Il y a un autre résultat de dérandomisation pour par Gutfreund, Shaltiel et Ta-Shma (Dureté uniforme vs aléatoire pour les jeux Arthur-Merlin, dans Computational Complexity 12 (3-4): 85-130, 2003). Ce résultat fonctionne sous des hypothèses de dureté uniformes (avec la mise en garde io habituelle). UNEMcoUNEM
Alon Rosen
5

Que diriez-vous de la gamme (c.-à-d. Liste, une entrée par front) des résistances efficaces? La résistance effective d'un bord est la probabilité que le bord se trouve dans un arbre s'étendant au hasard. Des résistances efficaces peuvent être trouvées en utilisant des algorithmes de Spielman et Teng, bien que je ne sache pas à quel point il est facile à mettre en œuvre (si l'on voulait faire des expériences).

Supposons que nous ayons deux graphes fortement réguliers, qui ont les mêmes valeurs propres (et nous savons que les valeurs propres ne distinguent pas nécessairement les graphiques non isomorphes). Ensuite, si les résistances effectives (c'est-à-dire les listes, encore) sont les mêmes, elles ne peuvent pas être utilisées pour distinguer les graphiques. Mais pourquoi deux graphes co-spectraux auraient-ils la même distribution de leurs bords dans des arbres s'étendant au hasard? Existe-t-il un lien connu entre le spectre du graphe et les résistances effectives d'un graphe? c'est-à-dire en connaissant le spectre du graphe, peut-on calculer les résistances effectives?

astérix
la source
-1

Il pourrait être intéressant de souligner que si GI n'est pas en coNP alors P ≠ NP.

1) Si GI n'est pas en coNp alors GI ≠ NGI

2) Si GI ≠ NGI alors GI ≠ P

3) Si GI ≠ P alors P ≠ NP

En corollaire des propositions on a: si GI n'est pas en coNP alors P ≠ NP. Il en va de même si NGI n'est pas dans NP.

Francesco Cris
la source
1
C'est un peu trivial et vaut pour tout problème de NP.
Kaveh