Testkomplexität, wenn sich zwei Mengen von

Stellen Sie sich vor, wir haben zwei Mengen von Punkten der Größe . Was ist (zeitliche) Komplexität von Tests, wenn sie sich nur durch Rotation unterscheiden? : Es Rotationsmatrix existiert , so daß ?$m$$X,Y\subset \mathbb{R}^n$$OO^T=O^TO=I$$X=OY$

Hier geht es darum, reelle Werte darzustellen - der Einfachheit halber wird angenommen, dass es für jede Koordinate eine (kurze) algebraische Formel gibt, so dass die Kosten für grundlegende arithmetische Operationen als O (1) angenommen werden können.

Die grundlegende Frage ist, ob dieses Problem in P ist?

Während dieses Problem auf den ersten Blick einfach zu sein scheint - normalerweise reicht es aus, Normen der Punkte und lokale Beziehungen wie Winkel zu testen, gibt es böse Beispiele, bei denen es z. B. dem Problem der Graphisomorphie entspricht .

Speziell bei Betrachtung der Eigenräume der Adjazenzmatrix stark regelmäßiger Graphen (SRG) können wir diese geometrisch interpretieren . Im Folgenden finden Sie das einfachste Beispiel: Zwei SRGs mit 16 Scheitelpunkten, die lokal identisch aussehen, aber nicht isomorph sind:

Die Adjazenzmatrix von SRGs hat immer nur drei Eigenwerte (mit bekannten Formeln) - betrachtet man den Eigenraum für den obigen Eigenwert 2 (Kern von ), hat sie die Dimension 6 - der oben geschriebenen Basis. Wenn wir es orthonormalisieren (Gram-Schmidt), erhalten wir einen großen Raum möglicher orthonormaler Basen - unterschiedlich durch O ( 6 ) -Drehung, die "vertikale Vektoren" dreht: 16 der Länge 6. Definieren Sie eine Menge von Vektoren als X ⊂ R 6 , | X | = 16 hier und Y entsprechend für den zweiten Graphen - Umwandlung der Isomorphie des Graphen in Frage, wenn X und$A-2I$$O(6)$$X\subset \mathbb{R}^6$$|X|=16$$Y$$X$ unterscheiden sich nur durch Rotation.$Y$

Die Schwierigkeit besteht darin, dass alle diese Punkte in einer Kugel liegen und die ursprünglichen Beziehungen wiederherstellen: Alle Nachbarn (6 hier) befinden sich in einem festen Winkel <90 Grad, alle Nicht-Nachbarn (9 hier) in einem anderen festen Winkel> 90 Grad, wie im Schema Bild oben.

Das Testen auf der Grundlage von Norm- und lokalen Winkeln führt also zum Problem des Graphisomorphismus zurück. Die geometrische Interpretation ermöglicht es jedoch, globale Eigenschaften wie Rotationsinvarianten zu bearbeiten .

Im Allgemeinen versucht ein natürlicher "globaler" Ansatz, beide Mengen "Modulo-Rotation" (die Freiheitsgrade enthält) zu beschreiben und dann nur zu überprüfen, ob beide Beschreibungen identisch sind.$n(n-1)/2$

Wir können normalerweise Rotationsinvarianten definieren - die Frage ist, eine vollständige Menge von Rotationsinvarianten zu konstruieren: eine vollständige Menge von Modulo-Rotationen zu bestimmen.

Während ich keine Möglichkeit gefunden habe, Rotationsinvarianten direkt an Punkten (?) Zu arbeiten, kann dies für Polynome ( Stapel ) durchgeführt werden. Für das Grad 2-Polynom ist eine vollständige Basis der Rotationsinvarianten z. B. T r ( A k ) für k = 1 , … , n . Diagrammatisch können sie als Länge k- Zyklus dargestellt werden, und wir können analog Rotationsinvarianten für Polynome höherer Ordnung konstruieren (die verbleibende Frage ist ihre Unabhängigkeit), z$x^T A x$$Tr(A^k)$$k=1,\ldots,n$$k$Jedes Diagramm unten entspricht einer einzelnen Rotationsinvariante mit einem Polynom vom Grad 1,2,3,4 :

Die Frage ist , wie eine Reihe von Punkten mit einem Polynom zu beschreiben - in der Regel wir hohen Grad Polynome benötigen, zB , sondern setzt für SRGs sind ziemlich regelmäßig - Dose mit einem Polynom 6. Grades beschrieben werden:$p(z)=\prod_{x\in X} (x\cdot (z-x))$

wobei a , b , c Norm und Winkel in Mengen beschreiben, die für eine gegebene SRG erhalten wurden ( sind bekannt).

Können wir also testen, ob sich zwei Polynome vom Grad 6 nur durch Rotation in der Polynomzeit unterscheiden? Wenn ja, ist der Graphisomorphismus für SRGs in P.

Gibt es härtere Beispiele (zum Testen, ob sich zwei Sätze nur durch Rotation unterscheiden) als von SRGs? Ich bezweifle, dass Babai (?) Quasi-polynomielle Obergrenzen zulässt.

Update : Mir wurde auf Ähnlichkeit mit (gelöstem) orthogonalem Procrustes-Problem hingewiesen :

aus Singularwertzerlegung. Wir könnten diese Matrizen aus unseren Punkten konstruieren, es würde jedoch erforderlich sein, die Reihenfolge zu kennen - die wir nicht kennen und es gibt Möglichkeiten.$m!$

Wir könnten zB Monte-Carlo oder einen genetischen Algorithmus ausprobieren: Umschalten einiger Punkte und Testen der Entfernungsverbesserung unter Verwendung der obigen Formel. Ich vermute jedoch, dass ein solcher heuristischer Algorithmus eine exponentielle Anzahl lokaler Minima (?) Hat.

$\mathsf{P}$$\mathsf{P}$durch den Ansatz, den Sie vorschlagen. Die Tatsache, dass die kubische Formäquivalenz bereits deutlich schwerer zu sein scheint als GI (z. B. wissen wir immer noch nicht, ob der Algebraisomorphismus im Gegensatz zu GI quasi-poly-zeitlich ist), legt nahe, dass (a) Menschen über diesen Ansatz nachgedacht haben und (b) ihn haben ist noch offen.

Obwohl ich nicht sicher bin, ob ähnliche Ergebnisse für die orthogonale Gruppe zutreffen, wäre ich überrascht, wenn sie nicht zutreffen (insbesondere, wenn Sie von Grad 3 zu Grad 6 wechseln).