Złożoność testowania, jeśli dwa zestawy

Wyobraźmy sobie, że mamy dwa zestawy rozmiarów punktów . Jaka jest (czasowa) złożoność testowania, jeśli różnią się one tylko rotacją? : istnieje macierz rotacji taka, że ? $m$ $X,Y\subset \mathbb{R}^n$ $OO^T=O^TO=I$ $X=OY$

Istnieje tutaj problem reprezentowania rzeczywistych wartości - dla uproszczenia załóżmy, że dla każdej współrzędnej istnieje (krótki) wzór algebraiczny, tak że koszt podstawowych operacji arytmetycznych można przyjąć jako O (1).

Podstawowe pytanie brzmi, czy ten problem występuje w P?

Chociaż na pierwszy rzut oka problem ten może wydawać się prosty - zwykle wystarczy przetestowanie norm punktów i relacji lokalnych, takich jak kąty, istnieją nieprzyjemne przykłady, w których jest on np. Równoważny z problemem izomorfizmu grafów .

W szczególności, patrząc na przestrzenie własne macierzy przylegania silnie regularnych grafów (SRG), możemy nadać jej interpretację geometryczną . Poniżej znajduje się najprostszy przykład - dwa SRG z 16 wierzchołkami, które lokalnie wyglądają identycznie, ale nie są izomorficzne:

Macierz adiakencji SRG ma zawsze tylko trzy wartości własne (znanych wzorów) - patrząc na przestrzeń własną dla wartości własnej 2 powyżej (jądro ), ma wymiar 6 - podstawy zapisanej powyżej. Ortonormalizując go (Gram-Schmidt), otrzymujemy dużą przestrzeń możliwych podstaw ortonormalnych - różniących się obrotem , który obraca „wektory pionowe”: 16 długości 6. Zdefiniuj taki zestaw wektorów jako , tutaj i $A-2I$ $O(6)$ $X\subset \mathbb{R}^6$ $|X|=16$ $Y$ odpowiednio dla drugiego wykresu - pytanie o izomorfizm wykresu przekształcającego w pytanie, czy i różnią się tylko obrotem. $X$ $Y$

Trudność polega na tym, że wszystkie te punkty znajdują się w kuli i odtwarzają oryginalne relacje: wszyscy sąsiedzi (tutaj 6) są pod stałym kątem <90 stopni, wszyscy nie sąsiedzi (tutaj 9) pod innym stałym kątem> 90 stopni, jak na schemacie zdjęcie powyżej.

Testy oparte na normie i lokalnych kątach sięgają wstecz do problemu izomorfizmu grafów ... ale interpretacja geometryczna pozwala pracować na właściwościach globalnych , takich jak niezmienniki rotacji.

Ogólnie rzecz biorąc, naturalne podejście „globalne” próbuje opisać oba zestawy „obrót modulo” (który zawiera stopnie swobody), a następnie po prostu sprawdzić, czy oba opisy są identyczne. $n(n-1)/2$

Zwykle możemy zdefiniować niezmienniki rotacji - pytanie polega na zbudowaniu pełnego zestawu niezmienników rotacji: całkowite określenie zestawu rotacji modulo.

Chociaż nie mogłem znaleźć sposobu na praktyczne niezmienniki rotacyjne działające bezpośrednio na punktach (?), Można to zrobić dla wielomianów ( stosu ). Dla wielomianu stopnia 2 , pełną podstawą niezmienników obrotu jest np. dla . Schematycznie można je przedstawić jako cykl długości , i analogicznie możemy konstruować niezmienniki rotacji dla wielomianów wyższego rzędu (pozostałym pytaniem jest ich niezależność), np. $x^T A x$ $Tr(A^k)$ $k=1,\ldots,n$ $k$ każdy wykres poniżej odpowiada niezmiennikowi o jednym obrocie wielomianu stopnia 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$

Czy możemy więc sprawdzić, czy wielomiany dwóch stopni 6 różnią się tylko rotacją w czasie wielomianowym? Jeśli tak, wykres izomorfizmu dla SRG jest w P.

Czy istnieją trudniejsze przykłady (do testowania, jeśli dwa zestawy różnią się tylko obrotem) niż w przypadku SRG? Wątpię, pozwalając na quasi-wielomianową górną granicę dzięki Babai (?)

Aktualizacja : Wskazano na podobieństwo do (rozwiązanego) problemu ortogonalnego 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$

z rozkładu wartości osobliwych. Z naszych punktów moglibyśmy konstruować te matryce, wymagałoby to jednak znajomości kolejności - której nie znamy i sąmożliwości. $m!$

Możemy spróbować np. Monte-Carlo lub algorytmu genetycznego: przełączanie niektórych punktów i testowanie poprawy odległości za pomocą powyższej formuły, jednak podejrzewam, że taki algorytm heurystyczny może mieć wykładniczą liczbę lokalnych minimów (?)

cc.complexity-theory complexity-classes graph-isomorphism computational-geometry high-dimensional-geometry Jarek Duda
źródło

Cóż, przykłady zabójców dla praktycznych algorytmów izomorfizmu grafów niekoniecznie są SRG. Istnieją dwa dokumenty Daniel neuen i Pascal Schweitzer, że ja tu omawiane , które dają obecnie najtrudniejsze przykłady. Moja dyskusja twierdzi, że „konstrukcja multipede ... jest w zasadzie normalną konstrukcją CFI stosowaną do nieukierowanego wielopłaszczyznowego hipergrrafu”. Ta konstrukcja jest dalej modyfikowana, aby stała się sztywna, co usuwa wszystkie automorfizmy. Nie był to wcześniej SRG, ale później zdecydowanie nie będzie SRG.

Thomas Klimpel

Myślę, że znalezienie głównych składników zestawów punktów i ich sprawdzenie pomogłoby, ponieważ transformacja PCA ma całkiem niezłe właściwości.

FazeL

ThomasKlimpel, czy mógłbyś powiedzieć coś o przestrzeniach własnych tych innych trudnych przykładów? @FazeL, wartości własne macierzy korelacji z PCA są przykładami niezmienników rotacji - warunki niezbędne do różnicowania tylko rotacją (banalne dla SRG). Problemem jest uzyskanie wystarczającego warunku, np. Poprzez pełną podstawę niezmienników rotacji - całkowite określenie ustawionego (lub wielomianowego) obrotu modulo. Oto ogólna konstrukcja wielomianów: arxiv.org/pdf/1801.01058 , pytanie brzmi: jak wybrać wystarczającą liczbę (znaną) niezmienników niezmiennych?

Jarek Duda

k

$k$

2^{k - 1}

$2^{k-1}$

2^{k - 1}

$2^{k-1}$

2

$2$

2^{k - 1}

$2^{k-1}$

$\mathsf{P}$ $\mathsf{P}$ według proponowanego podejścia. Jednak fakt, że równoważność formy sześciennej wydaje się już znacznie trudniejsza niż GI (np. Wciąż nie wiemy, czy izomorfizm algebry jest w czasie quasi-poli, w przeciwieństwie do GI) sugeruje, że (a) ludzie pomyśleli o tym podejściu i (b) to jest nadal otwarty.

Chociaż nie jestem pewien, czy podobne wyniki odnoszą się do grupy ortogonalnej, byłbym zaskoczony, gdyby się nie utrzymywały (szczególnie jeśli przejdziesz od stopnia 3 do stopnia 6).

Joshua Grochow
źródło

Dziękuję, widzę, że mam dużo do przeczytania. Czy testowanie różniące się obrotem wielomianów również stało się trudne dla stopnia trzeciego? Liczba współczynników wynosi O (dim ^ stopień), rotacja ma dim (dim-1) / 2 współczynniki, więc pełny opis rotacji modulo powinien dać niezależny niezmiennik rotacji O (dim ^ stopień). Wiem, jak konstruować niezmienniki rotacyjne ( arxiv.org/pdf/1801.01058 ), warunek niezależności wydaje się trudny do udowodnienia, ale wysoka zależność wydaje się mało prawdopodobna (?)

Jarek Duda

@JarekDuda: Ten sam argument, który podałeś w komentarzu, miałby zastosowanie do ogólnej równoważności liniowej, z tym wyjątkiem, że zamiast miałbyś , ale oba są . .. Zależność między niezmiennikami jest często bardzo głębokim pytaniem. Ponadto nie chodzi tylko o to, ile niezależnych niezmienników potrzebujesz, ale (a) czy możesz obliczyć, które niezmienniki są potrzebne w czasie wieloczasowym, i (b) czy możesz nawet obliczyć wartość każdego takiego niezmiennika w czasie wielozmiennym?

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

$\binom{dim}{2}$

d i m^{2}

$dim^2$

Θ (d i m^{2})

$\Theta(dim^2)$

Joshua Grochow

Jasne, jeśli tylko jestem w stanie zbudować dużą liczbę niezmienników - chociaż nie wiem, czy jest to prawdą w przypadku innych typów równoważności (?), W przypadku niezmienników rotacyjnych istnieje konstrukcja, w której każdy wykres daje jeden niezmiennik, i istnieją systematyczne konstrukcje duże liczby np. analogicznie do długości wykresów cyklu k dla niezmiennej Tr (A ^ k) dla wielomianu stopnia 2 x ^ T Ax. W przypadku wielomianu o stałym stopniu możemy wyprodukować wystarczającą liczbę (lub znacznie więcej) niezmienników w czasie wieloczasowym - pozostałym problemem jest zapewnienie wystarczającej liczby niezależnych spośród nich.

Jarek Duda

Złożoność testowania, jeśli dwa zestawy

Odpowiedzi: