Pertimbangkan masalah-masalah berikut:
Masalah Vektor Orthogonal
Input: Satu set dari Boolean vektor masing-masing panjang .S
S nn dd Pertanyaan: Apakah ada vektor berbeda dan sehingga ?v 1
v1 v 2 ∈ Sv2∈S v 1 ⋅ v 2 = 0v1⋅v2=0 Masalah Vektor Non-Ortogonal
Input: Satu set dari Boolean vektor masing-masing dengan panjang dan bilangan bulat positif .S
S nn dd kk Pertanyaan: Apakah ada vektor yang berbeda dan sehingga ?v 1
v1 v 2 ∈ Sv2∈S v 1 ⋅ v 2 ≥ kv1⋅v2≥k
Apa hubungan kedua masalah ini?
Secara khusus, berikut adalah beberapa pertanyaan spesifik yang saya ingin tahu tentang:
(1) Apakah salah satu dari masalah ini tampaknya lebih sulit daripada yang lain?
(2) Saya tidak yakin seperti apa algoritma saat ini untuk OVP, tetapi untuk salah satu dari masalah ini, dapatkah Anda mendapatkan batas atas yang lebih baik daripada waktu ?O ( n 2 ⋅ d )
(3) Apakah memperbaiki membuat perbedaan untuk kompleksitas masalah kedua?k
Dengan , maksud saya produk dalam dari dan lebih dari .v 1 ⋅ v 2 v 1 v 2 R d
Sunting: Sebagian besar tanggapan menawarkan wawasan yang sangat bagus ketika kecil. d
d Apa yang bisa dikatakan ketika lebih besar? Ucapkan atau atau setidaknya untuk beberapa .d d = n d = √
d d=n n d=nαα>0d=n−−√ d=nα α>0
sumber
Jawaban:
Ketika diberikan sebagai bagian dari input, masalah kedua setara dengan masalah Max-IP monokromatik (diberikan , temukan ).k S ⊆ { 0 , 1 } d maks ( a , b ) ∈ S , a ≠ b a ⋅ bk S⊆ { 0 , 1 }d maks( a , b ) ∈ S, a ≠ ba ⋅ b
Baru-baru ini saya dan Ryan Williams memiliki (belum dipublikasikan) karya yang menunjukkan bahwa ketika , OVP dan versi bikromatik Max-IP (diberikan , temukan ), sebenarnya setara: yaitu, jika salah satu dari mereka memiliki algoritma waktu , begitu juga yang lain. (Pengurangan dari OVP ke Max-IP sudah terkenal, pengurangan baru di sini adalah dari Max-IP ke OVP).d = O ( log n ) A , B maks ( a , b ) ∈ A × B a ⋅ b n 2 - εd= O ( logn ) A , B maks( a , b ) ∈ A × Ba ⋅ b n2 - ε
Karena versi monokromatik Max-IP dapat direduksi menjadi versi bikromatik, hasil di atas juga menyiratkan bahwa ketika , monokromatik Max-IP dapat direduksi menjadi OVP.d = O ( log n )d= O ( logn )
Saya percaya ini adalah pertanyaan terbuka bahwa apakah OVP dapat direduksi menjadi Max-IP monokromatik. Ini juga terkait erat dengan penetapan kekerasan-OV untuk masalah pasangan terdekat (lihat mis. Pada Kompleksitas Pasangan Terdekat melalui Pair-Pasang Point-Sets )
Untuk Max-IP monokromatik, ada algoritma dengan waktu berjalan algoritma waktu oleh Alman, Chan dan Williams ( juga ditunjukkan oleh Rasmus), yang saya yakini canggih. Sedangkan algoritma terbaik untuk OVP berjalan dalam waktu saat , yang secara signifikan lebih cepat.n 2 - 1 / ~ O ( ( d / log n ) 1 / 3 ) n 2 - 1 / O ( log c ) d = c log nn2 - 1 / O˜( ( d/ logn )1 / 3) n2 - 1 / O ( logc ) d=clogn
Juga, versi perkiraan Max-IP juga dipelajari oleh makalah ini On The Hardness of Approximate dan Exact (Bichromatic) Maximum Inner Product , yang memberikan karakterisasi untuk kasus bikromatik (yaitu, untuk dimensi dan perkiraan rasio , masalahnya dapat diselesaikan dalam waktu ?). Algoritma dalam makalah itu juga berfungsi untuk kasus monokromatik.d t n 2 - εd t n2−ε
sumber
Jika saya percaya teknik Alman, Chan, dan Williams memberikan solusi yang paling dikenal untuk Masalah Vektor Non-Orthogonal. (Mereka mengutarakannya secara berbeda, sebagai masalah pasangan Hamming terdekat, tetapi ini setara dengan faktor poli ( ).)k = O ( log n ) dk=O(logn) d
Tanpa terikat pada , versi bikromatik dari Masalah Vektor Non-Orthogonal setidaknya sekeras Masalah Vektor Orthogonal (OVP) hingga faktor . Pertama, perhatikan bahwa dengan faktor overhead kita dapat mengurangi ke versi bikromatik OVP di mana (memisahkan serikat ke dalam set "warna" yang berbeda) dan kami hanya tertarik pada pasangan ortogonal bikromatik . Kedua, dengan faktor overhead kita dapat mengurangi ke kasus khusus dari bikromatik OVP di mana semua vektor di memiliki berat Hamming yang sama . Akhirnya, dengan membalik semua vektor di untuk mendapatkank d log n log n S = S 1 ∪ S 2 ( v 1 , v 2 ) ∈ S 1 × S 2 d S 1 w S 2 S ' 2 S 1 S 2 S 1 S ' 2 wk dlogn logn S=S1∪S2 (v1,v2)∈S1×S2 d S1 w S2 S′2 kita melihat bahwa dan memiliki pasangan ortogonal jika dan hanya jika dan memiliki sepasang vektor dengan dot produk setidaknya . Saya tidak yakin apakah ada pengurangan yang efisien dari Masalah Vektor Non-Ortogonik bikromatik ke versi monokromatik yang Anda jelaskan.S1 S2 S1 S′2 w
Jika Anda mengizinkan perkiraan ada sejumlah hasil terbaru untuk Masalah Vektor Non-Ortogonik bikromatik (sering disebut masalah Pencarian Produk Dalam Maksimum). Lihat misalnya makalah ini dan rujukannya.
sumber
Kesetaraan:
Algoritma Naif:
Jawab pertanyaan (2) & (3):
Pendekatan pertama:
Pendekatan kedua:
Pendekatan ketiga:
sumber