Complexidade do teste se dois conjuntos de

Imagine que temos dois conjuntos tamanho . Qual é a complexidade (tempo) dos testes se eles diferem apenas por rotação? : existe matriz de rotação tal que ? $m$ $X,Y\subset \mathbb{R}^n$ $OO^T=O^TO=I$ $X=OY$

Há uma questão de representar valores reais aqui - por simplicidade, assuma que existe (uma curta) fórmula algébrica para cada coordenada, de modo que o custo das operações aritméticas básicas possa ser assumido como O (1).

A questão básica é se esse problema está em P?

Embora, à primeira vista, esse problema possa parecer simples - geralmente é suficiente testar normas dos pontos e relações locais como ângulos, existem exemplos desagradáveis nos quais, por exemplo, é equivalente ao problema de isomorfismo gráfico .

Especificamente, observando os espaços próprios da matriz de adjacência de grafos fortemente regulares (SRG), podemos fornecer uma interpretação geométrica . Abaixo está o exemplo mais simples - dois SRGs de 16 vértices, que localmente parecem idênticos, mas não são isomórficos:

A matriz de adjacência dos SRGs sempre possui apenas três autovalores (de fórmulas conhecidas) - observando o espaço próprio para o autovalor 2 acima (núcleo de ), possui a dimensão 6 - da base escrita acima. Ortogonalizando-o (Gram-Schmidt), obtemos um grande espaço de possíveis bases ortonormais - diferindo pela rotação , que gira "vetores verticais": 16 de comprimento 6. Defina esse conjunto de vetores como , aqui, e correspondentemente para o segundo gráfico - convertendo a questão do isomorfismo do gráfico em questão se e $A-2I$ $O(6)$ $X\subset \mathbb{R}^6$ $|X|=16$ $Y$ $X$ difere apenas pela rotação. $Y$

A dificuldade é que todos esses pontos estão em uma esfera e recriam relações originais: todos os vizinhos (6 aqui) estão em ângulo fixo <90 graus, todos os não vizinhos (9 aqui) em outro ângulo fixo> 90 graus, como no esquema foto acima.

Portanto, testes baseados em normas e ângulos locais remontam ao problema de isomorfismo gráfico ... mas a interpretação geométrica permite trabalhar em propriedades globais como invariantes de rotação.

$n(n-1)/2$

Geralmente, podemos definir invariantes de rotação - a questão é construir um conjunto completo de invariantes de rotação: determinar completamente um conjunto de rotação de módulo.

$x^T A x$ $Tr(A^k)$ $k=1,\ldots,n$ $k$ cada gráfico abaixo corresponde a uma única rotação invariante de grau 1,2,3,4 polinomial :

$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$

Então, podemos testar se dois polinômios de grau 6 diferem apenas por rotação no tempo polinomial? Nesse caso, o isomorfismo gráfico para SRGs está em P.

Existem exemplos mais difíceis (para testar se dois conjuntos diferem apenas por rotação) do que os SRGs? Duvido, permitindo um limite superior quase polinomial graças a Babai (?)

Atualização : fui apontada similaridade com o problema (resolvido) ortogonal de Procrustes :

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$

da decomposição de valor singular. Poderíamos construir essas matrizes a partir de nossos pontos, no entanto, seria necessário conhecer a ordem - que não sabemos e existempossibilidades. $m!$

Poderíamos tentar, por exemplo, Monte-Carlo ou algoritmo genético: alternar alguns pontos e testar a melhoria da distância usando a fórmula acima, no entanto, suspeito que esse algoritmo heurístico possa ter um número exponencial de mínimos locais (?)

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

Bem, os exemplos matadores de algoritmos práticos de isomorfismo de grafos não são necessariamente SRGs. Existem dois artigos de Daniel Neuen e Pascal Schweitzer que discuti aqui , que dão os exemplos mais difíceis atualmente. Minha discussão afirma que "a construção multípede ... é basicamente a construção CFI normal aplicada a um hipergrafo de várias arestas não direcionado". Essa construção é modificada para torná-la rígida, o que remove todos os automorfismos. Não era um SRG antes, mas depois definitivamente não será um SRG.

Thomas Klimpel

Acho que encontrar os principais componentes dos conjuntos de pontos e verificá-los ajudaria, pois a transformação do PCA possui algumas propriedades bastante interessantes.

Fazel

ThomasKlimpel, você poderia dizer algo sobre os espaços próprios desses outros exemplos difíceis? @FazeL, os autovalores da matriz de correlação do PCA são exemplos de invariantes de rotação - condições necessárias para diferir apenas pela rotação (trivial para SRGs). O problema é obter uma condição suficiente, por exemplo, através de uma base completa de invariantes de rotação - determinando completamente a rotação do módulo (ou polinomial). Aqui está uma construção geral para polinômios: arxiv.org/pdf/1801.01058 , a questão é como escolher um número suficiente (conhecido) de invariantes independentes?

Dongik Duda

Esses gráficos já estão coloridos. Para fixo , existem cores para as quais nós têm essa cor e cores para as quais 2 nós têm essa cor. Em termos de espaços próprios, isso significa que você tem muitos espaços próprios da dimensão e ainda mais espaços pessoais da dimensão . Pelo menos é o que acontece se a construção do CFI for aplicada a um gráfico não-direcionado k-regular. (Mas não se preocupe, isomorfismo de SRG é um problema em aberto também.)

k

$k$

2^{k - 1}

$2^{k-1}$

2^{k - 1}

$2^{k-1}$

2

$2$

Thomas Klimpel

Os espaços eigens da dimensão podem realmente se separar em espaços eigens ainda menores, pois mesmo para SRG, temos mais de um eigenspace, mas a lógica acima sugere que existe apenas um único eigenspace. Dê uma olhada na figura 4.2 no artigo mais curto (mais teórico), para ver / entender como esses gráficos se parecem.

2^{k - 1}

$2^{k-1}$

Thomas Klimpel

Eu acho que isso está aberto. Observe que se, em vez de testar a equivalência sob rotações, você pedir equivalência no grupo linear geral, já testar a equivalência de polinômios de grau três é GI-difícil ( Agrawal-Saxena STACS '06 , versão livremente disponível do autor ) e, de fato, está em menos difícil do que testar o isomorfismo das álgebras. Agora, a dureza GI não é evidência de que seu problema não está em ; na verdade, todas as suas perguntas são essencialmente se podemos colocar GI em $\mathsf{P}$ $\mathsf{P}$ pela abordagem que você sugere. No entanto, o fato de a equivalência da forma cúbica já parecer significativamente mais difícil do que o IG (por exemplo, ainda não sabemos se o isomorfismo da álgebra está no tempo quase poli, ao contrário do IG) sugere que (a) as pessoas pensaram nessa abordagem e (b) ainda está aberto.

Embora eu não tenha certeza se resultados semelhantes são válidos para o grupo ortogonal, eu ficaria surpreso se eles não fossem válidos (especialmente se você passar do grau 3 para o grau 6).

Joshua Grochow
fonte

Obrigado, vejo que tenho muito o que ler. Os testes diferentes pela rotação de polinômios também se tornaram difíceis para o grau três? O número de coeficientes é O (dim ^ grau), a rotação possui coeficientes dim (dim-1) / 2; portanto, a rotação completa do módulo de descrição deve ser dada por invariantes de rotação independentes O (dim ^ grau). Eu sei como construir invariantes de rotação ( arxiv.org/pdf/1801.01058 ), a condição de independência parece difícil de provar, mas elevada dependência parecer improvável (?)

Jarek Duda

@JarekDuda: O mesmo argumento que você faz no seu comentário se aplica à equivalência linear geral, exceto que, em vez dos coeficientes , você teria , mas esses são . .. Dependência entre invariantes é frequentemente uma questão muito profunda. Além disso, não é apenas uma questão de quantos invariantes independentes você precisa, mas (a) você pode calcular quais invariantes você precisa no tempo da poli e (b) você pode até calcular o valor de cada um desses invariantes no tempo da poli?

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

$\binom{dim}{2}$

d i m^{2}

$dim^2$

Θ (d i m^{2})

$\Theta(dim^2)$

Joshua Grochow

Claro, se apenas for capaz de construir um grande número de invariantes - embora eu não saiba se isso é verdade para outros tipos de equivalência (?), Para os invariantes de rotação, há uma construção em que cada gráfico dá uma invariável e há construções sistemáticas de números grandes, por exemplo, por analogia aos gráficos de comprimento k do ciclo para Tr (A ^ k) invariante para o polinômio grau 2 x ^ T Ax. Para polinômios de grau fixo, podemos produzir um número suficiente (ou muito mais) de invariantes no tempo poli - o problema restante é garantir um número suficiente de independentes entre eles.

Jarek Duda 24/02

Complexidade do teste se dois conjuntos de

Respostas: