Kompleksitas pengujian jika dua set titik

Bayangkan kita memiliki dua set ukuran $m$ dari titik $X,Y\subset \mathbb{R}^n$ . Apa kerumitan (waktu) pengujian jika perbedaannya hanya berdasarkan rotasi? : ada matriks rotasi $OO^T=O^TO=I$ sedemikian rupa sehingga $X=OY$ ?

Ada masalah yang mewakili nilai-nilai nyata di sini - untuk kesederhanaan anggap bahwa ada (pendek) rumus aljabar untuk setiap koordinat, sehingga biaya operasi aritmatika dasar dapat diasumsikan sebagai O (1).

Pertanyaan dasarnya adalah apakah masalah ini ada di P?

Sementara pada pandangan pertama masalah ini mungkin tampak sederhana - biasanya cukup untuk menguji norma-norma titik dan hubungan lokal seperti sudut, ada contoh buruk di mana itu misalnya setara dengan masalah grafik isomorfisme .

Secara khusus, melihat eigenspaces dari matriks adjacency dari grafik sangat teratur (SRG), kita dapat memberikan interpretasi geometris . Di bawah ini adalah contoh paling sederhana - dua SRG titik 16, yang secara lokal terlihat identik, tetapi tidak isomorfik:

Matriks adjacency dari SRG selalu hanya memiliki tiga nilai eigen (dari rumus yang diketahui) - melihat eigenspace untuk nilai eigen 2 di atas (kernel ), ia memiliki dimensi 6 - dasar yang ditulis di atas. Orthonormalizing itu (Gram-Schmidt), kita mendapatkan ruang besar kemungkinan basis ortonormal - berbeda dengan rotasi, yang berputar "vektor vertikal": 16 panjang 6. Tentukan set seperti vektor seperti , sini, dan sesuai untuk grafik kedua - mengubah pertanyaan grafik isomorfisme menjadi pertanyaan jika dan $A-2I$ $O(6)$ $X\subset \mathbb{R}^6$ $|X|=16$ $Y$ $X$ berbeda hanya dengan rotasi. $Y$

Kesulitannya adalah bahwa semua titik-titik ini berada dalam bola dan menciptakan kembali hubungan asli: semua tetangga (6 di sini) berada dalam sudut tetap <90 derajat, semua non-tetangga (9 di sini) di sudut tetap lain> 90 derajat, seperti dalam skema gambar di atas.

Jadi pengujian berdasarkan norma dan sudut lokal membutuhkan kembali ke grafik masalah isomorfisme ... tetapi interpretasi geometris memungkinkan untuk bekerja pada properti global seperti invarian rotasi.

$n(n-1)/2$

Kita biasanya dapat mendefinisikan invarian rotasi - pertanyaannya adalah membangun seperangkat invaraints rotasi lengkap: sepenuhnya menentukan rotasi set modulo.

$x^T A x$ $Tr(A^k)$ $k=1,\ldots,n$ $k$ setiap grafik di bawah ini sesuai dengan invarian rotasi tunggal dengan derajat 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$

Jadi dapatkah kita menguji apakah polinomial dua derajat 6 hanya berbeda dengan rotasi dalam waktu polinomial? Jika demikian, isomorfisme grafik untuk SRG ada dalam P.

Apakah ada contoh yang lebih sulit (untuk pengujian jika dua set hanya berbeda oleh rotasi) daripada dari SRG? Saya ragu, memungkinkan untuk batas atas kuasi polinomial berkat Babai (?)

Pembaruan : Saya menunjukkan kesamaan dengan masalah Procrust orthogonal (diselesaikan) :

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$

dari dekomposisi nilai singular. Kita dapat membangun matriks ini dari poin kita, namun, itu perlu mengetahui urutan - yang kita tidak tahu dan adakemungkinan. $m!$

Kita dapat mencoba misalnya Monte-Carlo atau algoritma genetika: mengganti beberapa titik dan menguji peningkatan jarak menggunakan rumus di atas, namun, saya menduga bahwa algoritma heuristik seperti itu mungkin memiliki jumlah eksponensial minimum lokal (?)

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

Nah, contoh pembunuh untuk algoritma isomorfisma grafik praktis belum tentu SRG. Ada dua makalah oleh Daniel Neuen dan Pascal Schweitzer yang saya diskusikan di sini , yang memberikan contoh paling sulit saat ini. Diskusi saya mengklaim bahwa "konstruksi berganda ... pada dasarnya adalah konstruksi CFI normal yang diterapkan pada multi-edge hypergraph". Konstruksi ini selanjutnya dimodifikasi untuk membuatnya kaku, yang menghilangkan semua automorfisme. Itu bukan SRG sebelumnya, tapi setelah itu pasti bukan SRG.

Thomas Klimpel

Saya pikir menemukan komponen utama dari set titik dan memeriksanya akan membantu karena transformasi PCA memiliki beberapa properti yang cukup bagus.

FazeL

Thomas Klimpel, dapatkah Anda mengatakan sesuatu tentang eigenspaces dari contoh sulit lainnya? @FazeL, nilai eigen dari matriks korelasi dari PCA adalah contoh invarian rotasi - kondisi yang diperlukan untuk berbeda hanya dengan rotasi (sepele untuk SRG). Masalahnya adalah untuk mendapatkan kondisi yang cukup, misalnya melalui basis invarian rotasi lengkap - sepenuhnya menentukan rotasi modulo set (atau polinomial). Berikut ini adalah konstruksi umum untuk polinomial: arxiv.org/pdf/1801.01058 , pertanyaannya adalah bagaimana memilih jumlah yang cukup (diketahui) dari invarian independen?

Jarek Duda

Grafik tersebut sudah diwarnai, Untuk tetap , ada warna yang memiliki simpul warna, dan warna yang 2 node memiliki warna itu. Dalam hal eigenspaces, ini berarti Anda mendapatkan banyak eigenspaces dimensi , dan bahkan lebih banyak eigenspaces dimensi . Setidaknya itulah yang terjadi jika konstruksi CFI diterapkan pada grafik tidak berarah k-regular. (Tapi jangan khawatir, isomorfisme SRG juga merupakan masalah terbuka.)

k

$k$

2^{k - 1}

$2^{k-1}$

2^{k - 1}

$2^{k-1}$

2

$2$

Thomas Klimpel

Eigenspaces dimensi mungkin benar-benar terpisah menjadi eigenspaces yang lebih kecil, karena bahkan untuk SRG, kami memiliki lebih dari 1 eigenspace, tetapi logika di atas menyarankan bahwa hanya ada satu eigenspace. Lihatlah gambar 4.2 dalam makalah yang lebih pendek (lebih teoretis), jadi lihat / pahami bagaimana grafiknya.

2^{k - 1}

$2^{k-1}$

Thomas Klimpel

Saya pikir ini terbuka. Perhatikan bahwa jika alih-alih menguji ekuivalensi di bawah rotasi Anda meminta ekuivalensi di bawah grup linear umum, maka yang sudah menguji ekuivalensi derajat tiga polinomial adalah GI-hard ( Agrawal-Saxena STACS '06 , versi penulis tersedia secara bebas ), dan pada kenyataannya berada pada Setidaknya sekeras menguji isomorfisma aljabar. Sekarang, kekerasan-GI bukanlah bukti bahwa masalah Anda tidak ada di , karena memang, seluruh pertanyaan Anda pada dasarnya adalah apakah kita dapat memasukkan GI ke dalam $\mathsf{P}$ $\mathsf{P}$ dengan pendekatan yang Anda sarankan. Namun, fakta bahwa persamaan bentuk kubik sudah tampak jauh lebih sulit daripada GI (misalnya kita masih tidak tahu apakah aljabar isomorfisma berada dalam waktu kuasi-poli, tidak seperti GI) menunjukkan bahwa (a) orang telah memikirkan pendekatan ini dan (b) masih terbuka.

Walaupun saya tidak tahu pasti apakah hasil yang sama berlaku untuk kelompok ortogonal, saya akan terkejut jika mereka tidak tahan (khususnya jika Anda pindah dari tingkat 3 ke tingkat 6).

Joshua Grochow
sumber

Terima kasih, saya melihat saya harus banyak membaca. Apakah pengujian berbeda dengan rotasi polinomial juga menjadi sulit untuk tingkat tiga? Jumlah koefisien adalah O (derajat redup), rotasi memiliki koefisien redup (redup-1) / 2, jadi deskripsi lengkap rotasi modulo harus diberikan oleh invarian rotasi independen O (redup). Saya tahu cara membuat invarian rotasi ( arxiv.org/pdf/1801.01058 ), kondisi independensi tampaknya sulit untuk dibuktikan, tetapi ketergantungan yang tinggi tampaknya tidak mungkin (?)

Jarek Duda

@JarekDuda: Argumen yang sama yang Anda buat dalam komentar Anda akan berlaku untuk kesetaraan linear umum, kecuali alih-alih koefisien Anda akan memiliki , tetapi keduanya adalah . .. Ketergantungan antar invarian seringkali merupakan pertanyaan yang sangat mendalam. Selain itu, ini bukan hanya pertanyaan tentang berapa banyak invarian independen yang Anda butuhkan, tetapi (a) dapatkah Anda menghitung invarian mana yang Anda butuhkan dalam waktu-poli, dan (b) dapatkah Anda menghitung nilai setiap invarian tersebut dalam waktu-waktu?

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

$\binom{dim}{2}$

d i m^{2}

$dim^2$

Θ (d i m^{2})

$\Theta(dim^2)$

Joshua Grochow

Tentu, jika hanya mampu membuat invarian dalam jumlah besar - sementara saya tidak tahu apakah itu benar untuk tipe kesetaraan lainnya (?), Untuk invarian rotasi ada konstruksi di mana setiap grafik memberikan satu invarian, dan ada konstruksi sistematis dari sejumlah besar misalnya dalam analogi panjang grafik siklus k untuk invarian Tr (A ^ k) untuk derajat 2 polinomial x ^ T Ax. Untuk polinomial tingkat tetap, kami dapat menghasilkan jumlah invarian yang cukup (atau lebih banyak) dalam waktu bersamaan - masalah yang tersisa adalah memastikan jumlah yang cukup dari yang independen di antara mereka.

Jarek Duda

Kompleksitas pengujian jika dua set titik

Jawaban: