Algorytmiczny problem wektorowy

Mam problem algebraiczny związany z wektorami w dziedzinie GF (2). Niech będą wektorami wymiaru , a . Znaleźć wielomianowej algorytm czasową znajdzie (0,1)-wektor tego samego wymiaru tak, że nie jest sumą każdy wektory między . Dodawanie wektorów odbywa się ponad polem GF (2), które ma dwa elementy 0 i 1 ( i ). n m = n O ( 1 )$v_1, v_2, \ldots, v_m$$n$$m=n^{O(1)}$$u$( log n ) O ( 1 ) v 1 , v 2 , … , v m 0 + 1 = 0 + 1 = 1 0 + 0 = 1 + 1 = $u$$(\log n)^{O(1)}$$v_1,v_2, \ldots, v_m$$0+1=0+1=1$$0+0=1+1=0$

Łatwo jest dostrzec istnienie takiego wektora za pomocą prostego argumentu liczącego. Czy możemy znaleźć w czasie wielomianowym? Znalezienie w czasie wykładniczym jest banalne . Wyślę nagrodę czekową w wysokości 200 USD za pierwsze prawidłowe rozwiązanie.$u$$u$

Wydaje się, że istnieje literówka; Zakładam, że masz zamiar znaleźć który nie jest sumą wektorów wśród (nie ). ( log n ) O ( 1 ) v 1 , … , v m$u \in \{0,1\}^n$$(\log n)^{O(1)}$$v_1,\dots, v_m$$n$

Nie jest dla mnie jasne, czy jakaś stała w działa dla Ciebie. Jeśli możesz zadowolić się sumami mniejszymi niż wektorów, być może jest coś do zrobienia. Ale jeśli chcesz, aby ta ilość była , to myślę, że jest to dość trudne (pracowałem nad tym problemem od dłuższego czasu). log m ( log m ) 1 + $(\log n)^{O(1)}$$\log m$$(\log m)^{1+\delta}$

Nadal możesz zainteresować się tym, że jest to przykład problemu zdalnego punktu Alona, ​​Panigrahy i Yekhanina („Deterministyczne algorytmy aproksymacyjne dla problemu najbliższego słowa kodowego”) dla niektórych parametrów. Niech i będą kolumnami macierzy kontroli parzystości kodu liniowego w wymiaru (jeśli ta macierz nie miała pełnej rangi problem byłby trywialny). Wtedy twój problem jest równoznaczny ze znalezieniem , czyli daleko od kodu. To ustawienie parametrów, w których wymiar jest bardzo zbliżony do m, nie zostało zbadane w pracy. Mogą jednak tylko osiągnąć oddaleniev 1 , … , v m { 0 , 1 } m d = m - n u ∈ { 0 , 1 } n ( log n ) O ( 1 ) log m d = c $m > n$$v_1,\dots,v_m$$\{0,1\}^m$$d = m - n$$u \in \{0,1\}^n$$(\log n)^{O(1)}$$\log m$do wymiaru dla pewnej stałej . W rzeczywistości nie sądzę, abyśmy znali jakiś certyfikat wielomianowy, który pozwala nam udowodnić, że jakiś wektor jest większy niż daleko od przestrzeni wymiaru , nie mówiąc już o znalezieniu to.$d = cm$ω ( log m ) Ω ( m $c$$\omega(\log m)$$\Omega(m)$

Innym połączeniem jest uczenie się parzystości w modelu błędnym. Jeśli można skutecznie nauczyć się -parities (zdefiniowanych na ) z błędem związanym ściśle mniej niż , wówczas można ustawić dowolne wartości na pierwsze bity i `` wymuszają błąd '' na ostatnim bicie, ustawiając wartość przeciwną do przewidywanej przez ucznia. Wydaje się to jednak znacznie silniejsze.0 , 1 m n n - 1 $(\log n)^{O(1)}$${0,1}^m$$n$$n - 1$$u$

Problem związany jest również z oddzieleniem EXP od niektórych redukcji do rzadkich zestawów.