Quelle preuve y a-t-il que l'isomorphisme graphique n'est pas dans

23

Motivé par le commentaire de Fortnow sur mon article, Preuve que le problème d'isomorphisme graphique n'est pas complet $NP$ , et par le fait que est un candidat principal pour le problème intermédiaire (pas complet ni en ), je suis intéressé par des preuves connues que se trouve pas dans . $GI$ $NP$ $NP$ $P$ $GI$ $P$

L'une de ces preuves est la complétude d'un problème d'automorphisme de graphe restreint (le problème d'automorphisme de graphe libre à virgule fixe est complet). Ce problème et d'autres généralisations de ont été étudiés dans " Quelques problèmes NP-complets similaires à l'isomorphisme graphique " par Lubiw. Certains peuvent soutenir comme preuve le fait que, malgré plus de 45 ans, personne n'a trouvé d'algorithme polynomial pour le . $NP$ $NP$ $GI$ $GI$

Quelles autres preuves devons-nous croire que l' n'est pas dans ? $GI$ $P$

cc.complexity-theory graph-isomorphism Mohammad Al-Turkistany
la source

2

L'isomorphisme sous-graphique est également NP-complet.

$\;$

1

Des preuves un peu faibles sont la classe croissante de problèmes qui sont équivalents à l'espace de journalisation à GI, mais aucun ne semble avoir d'algorithmes de polytime évidents. (Bien sûr, si l'un d'eux a un algorithme de polytime, alors ils le font tous.)

András Salamon

preuves circonstancielles similaires à P vs NP: des décennies d'optimisation des algorithmes GI, par exemple nauty qui ont encore des tendances du pire cas non vérifiables expérimentalement, apparemment principalement sur des graphiques réguliers aléatoires.

vzn

1

voir aussi les graphiques en dur pour les tests GI

vzn

Que pensez-vous de ceci? dharwadker.org/tevet/isomorphism

Anna Tomskova

11

Avant cette question, mon opinion était que l'isomorphisme graphique pourrait être en P, c'est-à-dire qu'il n'y a aucune preuve pour croire que l'IG n'est pas en P. Alors je me suis demandé ce qui compterait comme preuve pour moi: s'il y avait des algorithmes matures pour - isomorphisme de groupe qui a pleinement exploité la structure disponible des groupes et n'aurait toujours aucun espoir d'atteindre l'exécution polynomiale, alors je conviens que GI n'est probablement pas en P. Il existe des algorithmes connus qui exploitent la structure disponible comme les tests d'isomorphisme pour - groupes. d'O'Brien (1994) $p$ $p$ $p$ , mais je ne l'ai pas lu suffisamment en détail pour juger s'il exploite pleinement la structure disponible, ou s'il y a un espoir d'améliorer cet algorithme (sans exploiter la structure non évidente supplémentaire des groupes ) pour obtenir un runtime polynomial. $p$

Mais je savais que Dick Lipton avait appelé à l'action vers la fin de 2011 pour clarifier la complexité de calcul du problème d'isomorphisme de groupe en général, et du problème d'isomorphisme de groupe particulier. J'ai donc recherché sur Google $p$

site:https://rjlipton.wordpress.com group isomorphism

afin de voir si l'appel à l'action avait réussi. C'était en effet:

Le dernier article passe en revue un document qui permet l' exécution de pour certaines familles importantes de groupes, exploite une grande partie de la structure disponible et reconnaît le document susmentionné de 1994. Parce que le lié à l'exécution est à la fois compatible avec l'expérience que l'isomorphisme graphique n'est pas difficile dans la pratique, et avec l'expérience que personne n'est en mesure de proposer un algorithme de temps polynomial (même pour l'isomorphisme de groupe), cela peut être considéré comme une preuve que l'IG n'est pas dans P . $n^{O(\log \log n)}$ $n^{O(\log \log n)}$

Thomas Klimpel
la source

rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems est également apparu par ma recherche. Il cite le théorème 2 Graphique isomorphisme est dans . De plus, chaque problème de promesse dans appartient à tel que défini pour les problèmes de promesse. ${\mathsf{RP}^{\mathrm{MCSP}}}$ ${\mathsf{SZK}}$ ${\mathsf{BPP}^{\mathrm{MCSP}}}$ C'est la preuve que l'IG n'est pas complète en NP, mais ce n'était pas la question ici. Permettez-moi d'ajouter que je ne vois aucun problème avec la longueur ou le style de ma réponse, car j'interprète une demande de preuves comme une demande d'avis motivé.

Thomas Klimpel

5

Je ne suis pas ton raisonnement. Comment savoir que la "structure disponible" est "pleinement exploitée"? En fait, le document Grochow-Qiao ne suggère-t-il pas que beaucoup plus peut être fait avec les cours de cohomologie?

Sasho Nikolov

@SashoNikolov Par "structure disponible", j'entends la connaissance de la structure dans la communauté de théorie des groupes, les communautés apparentées et les publications existantes. Des exemples où la structure n'est pas "pleinement exploitée" sont des publications dont le but principal est de proposer un algorithme pratique et implémentable, qui s'arrête donc à un moment donné et mentionne simplement les limitations restantes sans indication claire si elles sont fondamentales. Le document Grochow-Qiao les a examinés et a attaqué directement la complexité informatique de l'isomorphisme de groupe, d'où ses résultats fournissent de bonnes preuves.

Thomas Klimpel

11

Le plus petit ensemble de permutations que vous devez vérifier pour vérifier qu'aucune permutation non triviale n'existe dans un cadre de boîte noire est meilleur que mais toujours exponentielle, OEIS A186202 . $n!$

Le nombre de bits nécessaires pour stocker un graphe non étiqueté est de $log_{2}$ . Voir Naor, Moni. "Représentation succincte des graphiques généraux sans étiquette." Mathématiques appliquées discrètes 28.3 (1990): 303-307. La preuve de la méthode de compression est un peu plus propre si je me souviens bien. Quoi qu'ilsoit, Appelons quimis. Soit ${n\choose 2}-n log(n) +O(n)$ $U$ pour les graphiques étiquetés. $L=2^{{n\choose 2}}$

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)

et si vous convertissez en exponentielles. Examiner simplement leurs signatures de type en mettant des graphiques sous forme canonique semble plus facile, mais comme indiqué ci-dessus, GC facilite l'IG. $U^L$ $Bool^{L^{L}}$

Chad Brewbaker
la source

Merci. Quelle est la force de ce type d'arguments?

Mohammad Al-Turkistany du

y a-t-il une référence à citer qui documente davantage ce lien?

vzn

3

@ MohammadAl-Turkistany: Il s'agit essentiellement d'un argument de complexité de requête. Mais les algorithmes connus, par exemple Babai-Luks 1983, ont déjà dépassé cette limite, je pense par une marge assez importante (quelque chose comme

contre

2^{n}

$2^n$

).

2^{\sqrt{n}}

$2^{\sqrt{n}}$

Joshua Grochow

1

@ChadBrewbaker: Si votre préoccupation est codée et la complexité moyenne des cas, je suis sûr que Nauty fait bien mieux que votre algorithme. (Notez que le plus connu minorant nauty est

(Miyazaki , 1996), et un algorithme poly-temps a été trouvé pour les graphiques Miyazaki. Une analyse de simple montre une limite inférieure de

sur votre algorithme.) De plus, GI est en temps linéaire dans le cas moyen (Babai-Kucera).

Ω (2^{n / 20})

$\Omega(2^{n/20})$

(3 / 2)^{n}

$(3/2)^n$

Joshua Grochow

2

@ MohammadAl-Turkistany: cette question m'a fait réfléchir plus profondément sur mes convictions sur la complexité de l'IG. Re: votre autre question, notez que s'il n'y a pas de réduction de Turing poly-temps (ou même plusieurs) de GI à GA alors P

NP.

\neq

$\neq$

Joshua Grochow

8

Kozen dans son journal, un problème de clique équivalent à isomorphisme graphique , donne une preuve que est pas dans . Ce qui suit est tiré du document: $GI$ $P$

"Néanmoins, il est probable que trouver un algorithme de temps polynomial pour l'isomorphisme de graphe sera aussi difficile que de trouver un algorithme de temps polynomial pour un problème NP-complet. À l'appui de cette affirmation, nous donnons un problème équivalent à l'isomorphisme de graphe, une petite perturbation dont NP-complet. "

De plus, Babai dans son récent article révolutionnaire Graph Isomorphism in quasipolynomial time donne un argument contre l'existence d'algorithmes efficaces pour GI. Il observe que le problème de isomorphisme de groupes (qui est réductible à GI) est un obstacle majeur à placer GI dans . Groupe problème Isomorphisme ( les groupes sont donnés par leur Cayley tableis) est résoluble en et on ne sait pas être en . $P$ $n^{O(\log n)}$ $P$

Voici un extrait de l'article de Babai:

Le résultat du présent article amplifie l'importance du problème d'isomorphisme de groupe (et du problème de défi énoncé) comme obstacle à la mise en place de l'IG en P. Il est fort possible que le statut intermédiaire de l'IG (ni NP-complet, ni temps polynomial) persistera.

Mohammad Al-Turkistany
la source

2

De Lem de Kozen. 3 on peut obtenir un exemple plus simple de ce phénomène: à savoir, l'isomorphisme de sous-graphe induit (est

un sous-graphe induit de

) est exactement GI quand

, mais est NP-difficile quand

pour tout

H

$H$

G

$G$

| G | = | H |

$|G|=|H|$

| G | = c | H |

$|G|=c|H|$

c > 1

$c > 1$ . Pour les paramètres discrets, nous savons qu'il existe des problèmes dans P qui deviennent rapidement NP-complets (par exemple 2SAT vs 3SAT). Savez-vous s'il existe des exemples de problèmes dans P avec certains paramètres continus qui deviennent NP-complets à un seuil précis? Si c'est le cas, ce genre de raisonnement ne serait pas une grande preuve que l'IG n'est pas en P, mais je ne peux pas penser à un tel exemple du haut de ma tête.

Joshua Grochow

2

@JoshuaGrochow Non, je n'ai pas connaissance de tels problèmes de décision. Mais pour des problèmes d'optimisation , je sais que trouver une affectation satisfaisant

des clauses est en

, tout en trouvant une affectation satisfaisant

des clauses est

-Hard même pour les formules satisfaisables de 3sat (

).

7 / 8

$7/8$

P

$P$

7 / 8 + ϵ

$7/8+ϵ$

N P

$NP$

ϵ > 0

$ϵ>0$

Mohammad Al-Turkistany

Oups, la réponse de Klimpel contient déjà la preuve d'isomorphisme de groupe. Quoi qu'il en soit, il est utile d'avoir le point de vue de Babai sur la question.

Mohammad Al-Turkistany

Babai a rétracté la revendication de l'exécution quasi-polynomiale . Apparemment, il y avait une erreur dans l'analyse.

Raphael

5

voici d'autres résultats pas encore cités

Sur la dureté de l'isomorphisme graphique / Torán FOCS 2000 et SIAM J. Comput. 33, 5 1093-1108.

Nous montrons que le problème d'isomorphisme du graphe est difficile sous DLOGTIME uniforme AC ⁰ réductions de plusieurs pour les classes de complexité NL, PL (espace logarithmique probabiliste) pour chaque espace modulaire logarithmique modulaire Mod _k L et pour la classe DET des problèmes NC ¹ réductibles à le déterminant. Ce sont les résultats de dureté connus les plus forts pour le problème d'isomorphisme graphique et impliquent une réduction d'espace logarithmique aléatoire du problème de correspondance parfaite à l'isomorphisme graphique. Nous étudions également les résultats de dureté pour le problème d'automorphisme des graphes.
L'isomorphisme du graphe n'est pas AC ⁰ réductible à l'isomorphisme de groupe / Chattopadhyay, Toran, Wagner

Nous donnons une nouvelle borne supérieure pour les problèmes d'isomorphisme de groupe et de quasigroupe lorsque les structures d'entrée sont données explicitement par des tables de multiplication. Nous montrons que ces problèmes peuvent être calculés par des circuits non déterministes de taille polynomiale de fan-in illimité avec une profondeur O (log log n) et O (log ² n) bits non déterministes, où n est le nombre d'éléments de groupe. Cela améliore la limite supérieure existante de [Wol94] pour les problèmes. Dans la limite supérieure précédente, les circuits ont borné les bits de fanin mais de profondeur O (log ² n) et également O (log ² n) non déterministes. Nous prouvons ensuite que le type de circuits de notre borne supérieure ne peut pas calculer la fonction de parité. Puisque la parité est AC ⁰réductible à l'isomorphisme graphique, cela implique que l'isomorphisme graphique est strictement plus difficile que l'isomorphisme de groupe ou de quasigroupe dans l'ordre défini par les réductions AC ⁰ .

vzn
la source

4

{A C}^{0}

$\mathsf{AC}^0$

Concernant les "bornes inférieures les plus fortes connues sur GI", ofc GI est dans NP donc une preuve réelle que GI n'est pas dans P est équivalente à P ≠ NP! (éventuellement via NPI ≠ ∅) ...

vzn

4

Oui, mais, par exemple, ce serait bien de savoir que le GI est P-dur! (Bien sûr, la dureté P a très peu à voir avec le fait de montrer que quelque chose n'est pas en P, mais cela suggérerait au moins que GI n'est pas en NC!)

Joshua Grochow

Quelle preuve y a-t-il que l'isomorphisme graphique n'est pas dans

Réponses: