Complexité des tests si deux ensembles de

Imaginons que nous ayons deux ensembles $m$ de points $X,Y\subset \mathbb{R}^n$ . Quelle est la complexité (temporelle) des tests s'ils diffèrent uniquement par la rotation? : il existe une matrice de rotation $OO^T=O^TO=I$ telle que $X=OY$ ?

Il y a un problème de représentation des valeurs réelles ici - pour simplifier, supposons qu'il existe (une courte) formule algébrique pour chaque coordonnée, de sorte que le coût des opérations arithmétiques de base peut être supposé comme O (1).

La question fondamentale est de savoir si ce problème est en P?

Alors qu'à première vue, ce problème peut sembler simple - il suffit généralement de tester les normes des points et les relations locales comme les angles, il existe de mauvais exemples où il est par exemple équivalent à un problème d'isomorphisme graphique .

Plus précisément, en regardant les espaces propres de la matrice d'adjacence des graphes fortement réguliers (SRG), nous pouvons lui donner une interprétation géométrique . Voici l'exemple le plus simple - deux SRG à 16 sommets, qui semblent localement identiques, mais qui ne sont pas isomorphes:

$A-2I$ $O(6)$ $X\subset \mathbb{R}^6$ $|X|=16$ $Y$ $X$ $Y$

La difficulté est que tous ces points sont dans une sphère et recréent des relations originales: tous les voisins (6 ici) sont dans un angle fixe <90 degrés, tous les non-voisins (9 ici) dans un autre angle fixe> 90 degrés, comme dans le schéma image ci-dessus.

Les tests basés sur les angles normaux et locaux reviennent donc au problème d'isomorphisme du graphe ... mais l'interprétation géométrique permet de travailler sur des propriétés globales comme les invariants de rotation.

$n(n-1)/2$

Nous pouvons généralement définir des invariants de rotation - la question est de construire un ensemble complet d'inaraints de rotation: déterminer complètement un ensemble de rotation modulo.

$x^T A x$ $Tr(A^k)$ $k=1,\ldots,n$ $k$ chaque graphique ci-dessous correspond à un seul invariant de rotation de polynôme de degré 1,2,3,4 :

$p(z)=\prod_{x\in X} (x\cdot (z-x))$

p (z) = \sum_{x \in X} (x \cdot z - a)^{2} (x \cdot z - b)^{2} (x \cdot z - c)^{2}

$p(z)=\sum_{x\in X} (x\cdot z -a)^2 (x\cdot z -b)^2 (x\cdot z -c)^2$

a, b, c

$a,b,c$

Alors pouvons-nous tester si deux polynômes de degré 6 ne diffèrent que par la rotation dans le temps polynomial? Si c'est le cas, l'isomorphisme du graphe pour les SRG est en P.

Existe-t-il des exemples plus difficiles (pour tester si deux ensembles ne diffèrent que par rotation) que ceux des SRG? J'en doute, permettant une borne supérieure quasi-polynomiale grâce à Babai (?)

Mise à jour : J'ai été pointé la similitude avec le problème (résolu) de procrustes orthogonaux :

min_{O : O^{T} O = I} ‖ O A - B ‖_{F} achieved for O = U V^{T}, where B A^{T} = U D V^{T}

$\min_{O:O^TO=I} \|OA-B\|_F \quad\textrm{achieved for}\quad O=UV^T,\quad\textrm{ where}\quad BA^T=UDV^T$

de la décomposition en valeurs singulières. Nous pourrions construire ces matrices à partir de nos points, cependant, il faudrait connaître l'ordre - que nous ne connaissons pas et il y en apossibilités. $m!$

Nous pourrions essayer par exemple Monte-Carlo ou un algorithme génétique: changer certains points et tester l'amélioration de la distance en utilisant la formule ci-dessus, cependant, je soupçonne qu'un tel algorithme heuristique pourrait avoir un nombre exponentiel de minima locaux (?)

cc.complexity-theory complexity-classes graph-isomorphism computational-geometry high-dimensional-geometry Jarek Duda
la source

Eh bien, les exemples de tueur pour les algorithmes d'isomorphisme de graphe pratiques ne sont pas nécessairement des SRG. Il y a deux articles de Daniel Neuen et Pascal Schweitzer dont j'ai discuté ici , qui donnent les exemples les plus difficiles actuellement. Ma discussion prétend que "la construction multipède ... est fondamentalement la construction CFI normale appliquée à un hypergraphe multi-bords non dirigé". Cette construction est encore modifiée pour la rendre rigide, ce qui supprime tous les automorphismes. Ce n'était pas un SRG avant, mais après ce ne sera certainement pas un SRG.

Thomas Klimpel

Je pense que trouver les principaux composants des ensembles de points et les vérifier serait utile car la transformation PCA a de très belles propriétés.

FazeL

ThomasKlimpel, pourriez-vous dire quelque chose sur les espaces propres de ces autres exemples difficiles? @FazeL, les valeurs propres de la matrice de corrélation de l'ACP sont des exemples d'invariants de rotation - conditions nécessaires pour ne différer que par rotation (trivial pour les SRG). Le problème est d'obtenir une condition suffisante, par exemple à travers une base complète d'invariants de rotation - déterminant complètement la rotation modulo d'ensemble (ou polynomiale). Voici une construction générale pour les polynômes: arxiv.org/pdf/1801.01058 , la question est de savoir comment choisir un nombre suffisant (connu) d'invariants indépendants?

Jarek Duda

Ces graphiques sont déjà colorés. Pour fixe , il y a des couleurs pour lesquelles nœuds ont cette couleur, et des couleurs pour lesquelles 2 nœuds ont cette couleur. En termes d'espaces propres, cela signifie que vous obtenez de nombreux espaces propres de dimension , et encore plus d'espaces propres de dimension . C'est du moins ce qui se passe si la construction CFI est appliquée à un graphe non orienté k-régulier. (Mais ne vous inquiétez pas, l'isomorphisme de SRG est également un problème ouvert.)

k

$k$

2^{k - 1}

$2^{k-1}$

2^{k - 1}

$2^{k-1}$

2

$2$

Thomas Klimpel

Les espaces propres de la dimension pourraient en fait se séparer en espaces propres encore plus petits, car même pour SRG, nous avons plus d'un espace propre, mais la logique ci-dessus suggère qu'il n'y a qu'un seul espace propre. Jetez un oeil à la figure 4.2 dans le document plus court (plus théorique), alors voyez / comprenez à quoi ressemblent ces graphiques.

2^{k - 1}

$2^{k-1}$

Thomas Klimpel

Je pense que c'est ouvert. Notez que si, au lieu de tester l'équivalence dans les rotations, vous demandez l'équivalence dans le groupe linéaire général, alors déjà tester l'équivalence des polynômes de degré trois est difficile (GI Agrawal-Saxena STACS '06 , la version gratuite de l'auteur ), et en fait est à moins difficile que de tester l'isomorphisme des algèbres. Maintenant, la dureté GI n'est pas une preuve que votre problème n'est pas dans , car en effet, toutes vos questions sont essentiellement de savoir si nous pouvons mettre GI dans $\mathsf{P}$ $\mathsf{P}$ par l'approche que vous proposez. Cependant, le fait que l'équivalence de forme cubique semble déjà beaucoup plus difficile que GI (par exemple, nous ne savons toujours pas si l'isomorphisme d'algèbre est en temps quasi-poly, contrairement au GI) suggère que (a) les gens ont pensé à cette approche et (b) elle est toujours ouvert.

Bien que je ne sais pas avec certitude si des résultats similaires sont valables pour le groupe orthogonal, je serais surpris s'ils ne le soient pas (en particulier si vous passez du degré 3 au degré 6).

Joshua Grochow
la source

Merci, je vois que j'ai beaucoup à lire. Les tests différant par la rotation des polynômes sont-ils également devenus difficiles pour le degré trois? Le nombre de coefficients est O (dim ^ degré), la rotation a des coefficients dim (dim-1) / 2, donc la description complète de la rotation modulo doit être donnée par des invariants de rotation indépendants O (dim ^ degré). Je sais comment construire des invariants de rotation ( arxiv.org/pdf/1801.01058 ), la condition d'indépendance semble difficile à prouver, mais une forte dépendance semble peu probable (?)

Jarek Duda

@JarekDuda: Le même argument que vous faites dans votre commentaire s'appliquerait à l'équivalence linéaire générale, sauf qu'au lieu des coefficients vous auriez , mais ce sont les deux . .. La dépendance entre les invariants est souvent une question très profonde. En outre, il ne s'agit pas seulement du nombre d'invariants indépendants dont vous avez besoin, mais (a) pouvez-vous calculer les invariants dont vous avez besoin en poly-temps, et (b) pouvez-vous même calculer la valeur de chacun de ces invariants en poly-temps?

(\binom{d i m}{2})

$\binom{dim}{2}$

d i m^{2}

$dim^2$

Θ (d i m^{2})

$\Theta(dim^2)$

Joshua Grochow

Bien sûr, si seulement on peut construire un grand nombre d'invariants - alors que je ne sais pas si c'est vrai pour d'autres types d'équivalence (?), Pour les invariants de rotation, il y a une construction où chaque graphique donne un invariant, et il y a des constructions systématiques de grands nombres, par exemple, par analogie avec les graphes de cycle de longueur k pour Tr (A ^ k) invariant pour le polynôme de degré 2 x ^ T Ax. Pour le polynôme à degré fixe, nous pouvons produire un nombre suffisant (ou beaucoup plus) d'invariants en poly-temps - le problème restant est d'assurer un nombre suffisant d'entre eux indépendants.

Jarek Duda le

Complexité des tests si deux ensembles de

Réponses: