¿Complejidad de la prueba si dos conjuntos de puntos en difieren solo por rotación?

Imaginemos que tenemos dos conjuntos de puntos tamaño . ¿Cuál es la complejidad (temporal) de las pruebas si difieren solo por rotación? : existe una matriz de rotación tal que ? $m$ $X,Y\subset \mathbb{R}^n$ $OO^T=O^TO=I$ $X=OY$

Hay un problema de representar valores reales aquí: por simplicidad, suponga que hay una fórmula algebraica (corta) para cada coordenada, de modo que el costo de las operaciones aritméticas básicas se puede asumir como O (1).

La pregunta básica es si este problema está en P?

Si bien, a primera vista, este problema puede parecer simple: por lo general, es suficiente para probar las normas de los puntos y las relaciones locales como los ángulos, hay ejemplos desagradables en los que es, por ejemplo, equivalente al problema de isomorfismo gráfico .

Específicamente, mirando los espacios propios de la matriz de adyacencia de gráficos fuertemente regulares (SRG), podemos darle una interpretación geométrica . A continuación se muestra el ejemplo más simple: dos SRG de 16 vértices, que localmente se ven idénticos, pero no son isomórficos:

La matriz de adyacencia de los SRG siempre tiene solo tres valores propios (de fórmulas conocidas): mirando el espacio propio para el valor propio 2 anterior (núcleo de ), tiene una dimensión 6, de base escrita anteriormente. Ortonormalizándolo (Gram-Schmidt), obtenemos un gran espacio de posibles bases ortonormales, que difieren en la rotación , que gira "vectores verticales": 16 de longitud 6. Defina un conjunto de vectores como , aquí, e correspondientemente para el segundo gráfico - convirtiendo la pregunta de isomorfismo del gráfico en pregunta si e difieren solo por rotación. $A-2I$ $O(6)$ $X\subset \mathbb{R}^6$ $|X|=16$ $Y$ $X$ $Y$

La dificultad es que todos estos puntos están en una esfera y recrean relaciones originales: todos los vecinos (6 aquí) están en ángulo fijo <90 grados, todos los no vecinos (9 aquí) en otro ángulo fijo> 90 grados, como en el esquema imagen de arriba.

Por lo tanto, las pruebas basadas en la norma y los ángulos locales se remontan al problema del isomorfismo gráfico ... pero la interpretación geométrica permite trabajar en propiedades globales como invariantes de rotación.

Generalmente, un enfoque "global" natural está tratando de describir ambos conjuntos de "rotación de módulo" (que contiene grados de libertad), y luego simplemente verifica si ambas descripciones son idénticas. $n(n-1)/2$

Por lo general, podemos definir invariantes de rotación : la pregunta es construir un conjunto completo de invariaciones de rotación: determinar completamente un conjunto de rotación de módulo.

Si bien no pude encontrar una forma para los invariantes de rotación prácticos que trabajan directamente en puntos (?), Se puede hacer para polinomios ( pila ). Para el polinomio de grado 2 , una base completa de invariantes de rotación es, por ejemplo, para . Diagramáticamente se pueden representar como un ciclo de longitud , y podemos construir de manera análoga invariantes de rotación para polinomios de orden superior (la pregunta restante es su independencia), por ejemplo, cada gráfico a continuación corresponde a un solo invariante de rotación de polinomio de grado 1,2,3,4 : $x^T A x$ $Tr(A^k)$ $k=1,\ldots,n$ $k$

La pregunta es cómo describir un conjunto de puntos con un polinomio: generalmente necesitamos polinomios de alto grado, Ej. , pero los conjuntos para SRG son bastante regular: se puede describir con solo polinomio de grado 6: $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$ donde describen norma y ángulos en conjuntos obtenidos para SRG dado (son conocidos).

a, b, c

$a,b,c$

Entonces, ¿podemos probar si dos polinomios de grado 6 difieren solo por rotación en el tiempo polinomial? Si es así, el isomorfismo gráfico para los SRG está en P.

¿Hay ejemplos más difíciles (para probar si dos conjuntos difieren solo por rotación) que los SRG? Lo dudo, permitiendo un límite superior casi polinomial gracias a Babai (?)

Actualización : me señalaron similitud con el problema de Procrustes ortogonal (resuelto) :

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 descomposición de valores singulares. Podríamos construir estas matrices a partir de nuestros puntos, sin embargo, requeriría conocer el orden, ¡lo cual no sabemos y hayposibilidades $m!$

Podríamos intentar, por ejemplo, Montecarlo o algoritmo genético: cambiar algunos puntos y probar la mejora de la distancia utilizando la fórmula anterior, sin embargo, sospecho que dicho algoritmo heurístico podría tener un número exponencial de mínimos locales (?)

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

Bueno, los ejemplos asesinos para algoritmos prácticos de isomorfismo de gráficos no son necesariamente SRG. Hay dos documentos de Daniel Neuen y Pascal Schweitzer que discutí aquí , que dan los ejemplos más difíciles actualmente. Mi discusión afirma que "la construcción multipede ... es básicamente la construcción CFI normal aplicada a una hipergrafía de múltiples bordes no dirigida". Esta construcción se modifica aún más para que sea rígida, lo que elimina todos los automorfismos. Antes no era un SRG, pero después definitivamente no será un SRG.

Thomas Klimpel

Creo que encontrar componentes principales de los conjuntos de puntos y verificarlos ayudaría, ya que la transformación de PCA tiene algunas propiedades bastante buenas.

FazeL

ThomasKlimpel, ¿podría decir algo sobre los espacios propios de estos otros ejemplos difíciles? @FazeL, los valores propios de la matriz de correlación de PCA son ejemplos de invariantes de rotación, condiciones necesarias para diferir solo por rotación (trivial para SRG). El problema es obtener una condición suficiente, por ejemplo, a través de una base completa de invariantes de rotación, determinando completamente la rotación del módulo establecido (o polinomial). Aquí hay una construcción general para polinomios: arxiv.org/pdf/1801.01058 , la pregunta es ¿cómo elegir el número suficiente (conocido) de invariantes independientes?

Jarek Duda

Esos gráficos ya están coloreados. Para fijo , hay colores para los que nodos tienen ese color y colores para los que 2 nodos tienen ese color. En términos de espacios propios, esto significa que obtienes muchos espacios propios de dimensión , e incluso más espacios propios de dimensión . Al menos eso es lo que sucede si la construcción CFI se aplica a un gráfico k-regular no dirigido. (Pero no se preocupe, el isomorfismo de SRG también es un problema abierto.)

k

$k$

2^{k - 1}

$2^{k-1}$

2^{k - 1}

$2^{k-1}$

2

$2$

Thomas Klimpel

Los espacios propios de la dimensión realidad podrían separarse en espacios propios aún más pequeños, ya que incluso para SRG, tenemos más de 1 espacio propio, pero la lógica anterior sugiere que solo hay un único espacio propio. Eche un vistazo a la figura 4.2 en el artículo más corto (más teórico), así que vea / comprenda cómo se ven esos gráficos.

2^{k - 1}

$2^{k-1}$

Thomas Klimpel

Creo que esto está abierto. Tenga en cuenta que si en lugar de probar la equivalencia bajo rotaciones, solicita equivalencia bajo el grupo lineal general, entonces probar la equivalencia de polinomios de grado tres es GI-duro ( Agrawal-Saxena STACS '06 , versión de libre acceso del autor ), y de hecho está en tan difícil como probar el isomorfismo de las álgebras. Ahora, la dureza GI no es evidencia de que su problema no esté en , ya que de hecho, todas sus preguntas son esencialmente si podemos poner GI en $\mathsf{P}$ $\mathsf{P}$ por el enfoque que sugieres. Sin embargo, el hecho de que la equivalencia de forma cúbica ya parece significativamente más difícil que GI (por ejemplo, todavía no sabemos si el isomorfismo de álgebra está en tiempo cuasi polivinílico, a diferencia de GI) sugiere que (a) las personas han pensado en este enfoque y (b) Todavía está abierto.

Si bien no estoy seguro si los resultados similares se mantienen para el grupo ortogonal, me sorprendería que no se mantuvieran (especialmente si pasa del grado 3 al grado 6).

Joshua Grochow
fuente

Gracias, veo que tengo mucho que leer. ¿Las pruebas que difieren por rotación de polinomios también se volvieron difíciles para el grado tres? El número de coeficientes es O (dim ^ grados), la rotación tiene coeficientes dim (dim-1) / 2, por lo que la descripción completa del módulo de rotación debe ser dada por O (dim ^ grados) invariantes de rotación independientes. Sé cómo construir invariantes de rotación ( arxiv.org/pdf/1801.01058 ), la condición de independencia parece difícil de probar, pero la alta dependencia parece poco probable (?)

Jarek Duda

@JarekDuda: el mismo argumento que hace en su comentario se aplicaría a la equivalencia lineal general, excepto en lugar de los coeficientes que tendría , pero ambos son . .. La dependencia entre invariantes es a menudo una pregunta muy profunda. Además, no es solo una cuestión de cuántos invariantes independientes necesita, sino que (a) puede calcular qué invariantes necesita en poli-tiempo, y (b) ¿puede incluso calcular el valor de cada uno de esos invariantes en poli-tiempo?

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

$\binom{dim}{2}$

d i m^{2}

$dim^2$

Θ (d i m^{2})

$\Theta(dim^2)$

Joshua Grochow

Claro, si solo es capaz de construir un gran número de invariantes, aunque no sé si es cierto para otros tipos de equivalencia (?), Para los invariantes de rotación hay una construcción en la que cada gráfico da un invariante, y hay construcciones sistemáticas de números grandes, p. ej., en analogía con la longitud k gráficos de ciclo para Tr (A ^ k) invariante para grado 2 polinomial x ^ T Ax. Para un polinomio de grado fijo, podemos producir un número suficiente (o mucho más) de invariantes en el tiempo polivinílico; el problema restante es garantizar un número suficiente de independientes entre ellos.

Jarek Duda

¿Complejidad de la prueba si dos conjuntos de puntos en difieren solo por rotación?

Respuestas: