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 ). $v_1, v_2, \ldots, v_m$ $n$ $m=n^{O(1)}$ $u$ $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$

ds.algorithms linear-algebra

— Bin Fu
źródło

wydaje się to niejasno związane z problemem sumy podzbiorów, który jest NP całkowity. używa to jednak pełnej liczby całkowitej zamiast XOR.

— vzn

co dziwne, ostatnio próbowałem sformułować i spojrzeć na podobny problem. spróbuj sek13.5 książki Stasys Jukna na temat złożoności funkcji boolowskiej. wygląda na to, że q można sformułować w odniesieniu do obwodów liniowych w tym rozdziale.

— vzn

co powiesz na algorytmy super-poli, tj. m ^ log (n)?

— Dimitris

@Niel de Beaudrap: ale liczba XORs, które musisz sprawdzić, jest super-poli (tj. Z grubsza ), a nie poli. Czy to nie problem?

(\binom{m}{\log (n)})

${{m}\choose{\log(n)}}$

— Dimitris

Aby rozszerzyć uwagę vzn: wydaje się, że prawie każdy wektor spełnia twoje wymagania, na podstawie tego samego argumentu liczenia. Wyobrażam sobie, że chciałbyś również dowodu, że (prawdopodobnie generowany losowo) wektor nie jest zawarty w żadnej podprzestrzeni rozpiętej przez polylog ( n ) wektorów: więc twoje pytanie jest równoznaczne z wykazaniem, że problem z określeniem, czy kandydat jest kandydatem, czy nie wektor u nie należy do podprzestrzeni generowanej przez jakiś wymiar f ( n ) ∈ polilog ( n ) wektorów jest w NP .

v_{j}

$\mathbf v_j$

— Niel de Beaudrap

Wydaje się, że istnieje literówka; Zakładam, że masz zamiar znaleźć który nie jest sumą wektorów wśród (nie ). $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 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ąć oddalenie $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$ $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. $(\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.

— David
źródło

Dzięki za wskazanie literówki. Ostatnim „v_n” powinno być „v_m”. Mam nadzieję, że ktoś to naprawi. Twoja odpowiedź zawiera przydatne informacje. +1

— Bin Fu