Masalah Vektor Algoritma

Saya memiliki masalah aljabar yang berhubungan dengan vektor di bidang GF (2). Misalkan menjadi (0,1) -vektor dimensi n , dan m = n O ( 1 ) . Cari algoritma waktu polinomial yang menemukan (0,1) -vector u dari dimensi yang sama seperti yang u bukanlah jumlah dari setiap ( log n ) O ( 1 ) vektor antara v 1 , v 2 , ... , $v_1, v_2, \ldots, v_m$$n$$m=n^{O(1)}$$u$$u$$(\log n)^{O(1)}$ . Penambahan vektor di atas bidang GF (2), yang memiliki dua elemen 0 dan 1 ( 0 + 1 = 0 + 1 = 1 , dan 0 + 0 = 1 + 1 = 0 ).$v_1,v_2, \ldots, v_m$$0+1=0+1=1$$0+0=1+1=0$

Sangat mudah untuk melihat keberadaan vektor seperti itu dengan argumen penghitungan yang sederhana. Bisakah kita menemukan dalam waktu polinomial? Sangat sepele untuk menemukan Anda dalam waktu eksponensial. Saya akan mengirimkan cek penghargaan $ 200 untuk solusi pertama yang benar.$u$$u$

Tampaknya ada kesalahan ketik; Saya berasumsi Anda bermaksud menemukan yang bukan jumlah ( log n ) O ( 1 ) vektor di antara v 1 , … , v m (bukan n ).$u \in \{0,1\}^n$$(\log n)^{O(1)}$$v_1,\dots, v_m$$n$

Tidak jelas bagi saya jika ada konstanta di bekerja untuk Anda. Jika Anda dapat menerima jumlah kurang dari vektor log m mungkin ada sesuatu yang harus dilakukan. Tetapi jika Anda ingin jumlah ini menjadi ( log m ) 1 + δ , maka saya pikir ini cukup sulit (saya telah mengerjakan masalah ini sejak lama).$(\log n)^{O(1)}$$\log m$$(\log m)^{1+\delta}$

Masih Anda mungkin tertarik untuk mengetahui bahwa ini adalah contoh dari Remote Point Problem dari Alon, Panigrahy dan Yekhanin ("Algoritma Perkiraan Deterministik untuk Masalah Codeword Terdekat") untuk parameter tertentu. Mari dan v 1 , ... , v m menjadi kolom dari matriks cek paritas dari kode linear di { 0 , 1 } m dari dimensi d = m - n (jika matriks ini tidak memiliki peringkat penuh, masalah akan sepele). Maka masalah Anda sama dengan menemukan u ∈ { 0 $m > n$$v_1,\dots,v_m$$\{0,1\}^m$$d = m - n$ yaitu ( log n ) O ( 1 ) -far dari kode. Pengaturan parameter ini, di mana dimensi sangat dekat dengan m, tidak dipelajari dalam makalah. Namun, mereka hanya bisa kita wajib keterpencilan log m hingga dimensi d = c m untuk beberapa konstan c . Faktanya, saya tidak berpikir kita mengetahui sertifikat berukuran polinomial yang memungkinkan kita untukmembuktikanbahwa beberapa vektor lebih dari ω ( log m ) -dari jauh dari ruang dimensi Ω ( m $u \in \{0,1\}^n$$(\log n)^{O(1)}$$\log m$$d = cm$$c$$\omega(\log m)$$\Omega(m)$, apalagi menemukannya.

Koneksi lain adalah dengan mempelajari paritas dalam model terikat kesalahan. Jika seseorang dapat secara efisien belajar -paritas (didefinisikan pada 0 , 1 m ) dengan kesalahan terikat kurang dari n , maka seseorang dapat mengatur nilai arbitrer ke n - 1 bit pertama dari u dan gaya `` force sebuah kesalahan '' pada bit terakhir dengan mengaturnya ke nilai yang berlawanan dengan yang diprediksi oleh pelajar. Ini tampaknya jauh lebih kuat.$(\log n)^{O(1)}$${0,1}^m$$n$$n - 1$$u$

Masalahnya juga terkait dengan memisahkan EXP dari reduksi tertentu ke set yang jarang.