$ mathbb {R} ^ n $の$ m $点の2つの集合が回転によってのみ異なる場合のテストの複雑さ?

私たちが$ X、Y subset mathbb {R} ^ n $点の2つの$ m $集合を持っているとします。
:回転行列$ OO ^ T = O ^ TO = I $が$ X = OY
$となるように存在するかどうかをテストの複雑さは何ですか?

ここでは実際の値を表す問題があります。簡単にするために、基本的な算術演算のコストをO(1)と仮定できるように、各座標に対して(短い)代数式があると仮定します。

基本的な質問は、この問題がPにあるかどうかです。


最初の見解では、この問題は単純なように思えるかもしれませんが、通常、ポイントのノルムと角度のような局所関係をテストするだけで十分です。厄介な例があります。グラフ同型問題と同等です

Specifically, looking at eigenspaces of adjacency matrix of
strongly regular graphs (SRG), we can give it geometrical
interpretation
. Below is the simplest example – two 16 vertex
SRGs, which locally look identical, but are not isomorphic:

enter image description here

SRGの隣接行列は、常に(既知の公式の)3つの固有値しか持ちません。上記の固有値2(カーネルは$ A-2I
$)の固有空間を見ます。 Orgnormalizing(Gram-Schmidt)では、$
O(6)$回転とは異なる可能性のある正規直交基底の大きな空間が得られます。これは、「垂直ベクトル」を回転させます:長さ16のベクトル。$
X subset $ X $と$ Y $がローテーションによってのみ異なる場合には、グラフ同型性質問を問題に変換する –
第2のグラフに対応して、mathbb {R} ^ 6 $、$ | X | = 16 $、

The difficulty is that all these points are in a sphere and
recreate original relations: all neighbors (6 here) are in fixed
angle <90 degrees, all non-neighbors (9 here) in another fixed
angle >90 degrees, like in the schematic picture above.

したがって、標準とローカルの角度に基づくテストは、グラフ同型問題に戻ります…しかし、幾何学的解釈は回転不変量のようなグローバルプロパティで作業することができます。


一般的に、自然な「グローバル」アプローチは、$ n(n-1)/ 2
$自由度を含む「モジュロローテーション」の両方のセットを記述しようとしています。同一である。

通常、 rotation invariants
を定義できます。この問題は、回転invaraintsの完全なセットを構築することです:モジュロローテーションを完全に決定すること。

実際の回転不変量が点(?)に直接作用する方法は見つけられませんでしたが、多項式(スタック)。次数2の多項式では、回転不変量の完全な基礎は、例えば次のようになる。
$ Tr(A ^ k)$は$ k = 1、 ldots、n $になります。図式的には長さ$ k $
cycleとして表すことができ、同様に高次多項式の回転不変量(残りの質問はその独立性です)、例えば下の各グラフは、次数1,2,3,4多項式の1つの回転不変量に対応します

enter image description here

問題は、多項式で点集合を記述する方法です。一般に、多項式を必要とします。 $ p(z)= prod_ {x in
X}(x cdot(z-x))$しかし、SRGのセットはかなり規則的です –
ちょうど6次の多項式で記述することができます:

$ 2 $(x cdot z -c)^ 2(x cdot z -c)^ 2(x cdot z -c)^ 2 $
ここで、$ a、b、c $は与えられたSRGについて得られた集合のノルムと角度を表す(知られている)。

So can we test if two degree 6 polynomials differ only
by rotation in polynomial time?
If so, graph isomorphism
for SRGs is in P.

Are there tougher examples (for testing if two sets
differ only by rotation) than from SRGs?
I doubt it,
allowing for quasi-polynomial upper bound thanks to Babai (?)


Update: I was pointed similarity with (solved)
orthogonal Procrustes problem:

OA-B | _F quad textrm {達成のために} quad O = UV ^ T、 quad
textrm {where} quad BA ^ T = UDV ^ T $$

特異値分解から。私たちはこれらの行列を私たちの点から構築することができましたが、順序を知る必要がありました。わかりませんが、$
m!$の可能性があります。

たとえば、モンテカルロまたは遺伝的アルゴリズム:いくつかの点を切り換え、上の公式を使用して距離の改善をテストすると、そのような発見的アルゴリズムは指数関数的な極小値を持つ可能性があります

ベストアンサー

私はこれが開いていると思う。回転のもとで等価性をテストする代わりに、一般的な線形グループの等価性を求めるなら、
3つの多項式の等価性をテストすることはGI-hard( Agrawal-Saxena STACS ’06著者の自由に利用可能なバージョン)、そして実際には代数の同型写像をテストすることと同じくらい難しいです。さて、GI硬度は、あなたの問題が$
mathsf {P} $にないという証拠ではありません。実際には、あなたが提案するアプローチによって、GIを$ mathsf
{P}
$に入れることができるかどうかということです。しかし、立方体の等価性がすでにGIよりもはるかに困難であるという事実(例えば、GIとは異なり、代数同型が擬ポリタイムであるかどうかはまだ分かっていない)は、(a)人々はこのアプローチを考えており、まだ開いています。

直交グループについても同様の結果が得られるかどうかはわかりませんが、それが成立しなければ驚くでしょう(特に、3位から6位に移行した場合)。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です