Struktura danych dla zapytań o minimalną liczbę kropek

$\mathbb{R}^n$$\langle \cdot, \cdot \rangle$$m$$v_1, v_2, \ldots, v_m$$x \in \mathbb{R}^n$$\min_i \langle x, v_i \rangle$$O(nm)$$n = 2$$O(\log^2 m)$

Jedyne, co mogę wymyślić, to: Bezpośrednią konsekwencją lematu Johnsona-Lindenstraussa jest to, że dla każdego i rozkładu na występuje liniowe mapowanie (które można ocenić w czasie ) tak, że . Tak więc w czasie O ((n + m) \ log m) możemy obliczyć$\varepsilon > 0$$\mathcal{D}$$\mathbb{R}^n$$f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$$O(n \log m)$$\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$$O((n + m) \log m)$coś , co jest w pewnym sensie zbliżone do $\min_i \langle x, v_i \rangle$ dla większości $x$ (przynajmniej jeśli normy $\|x\|$ i $\|v_i\|$ są małe).

UPD Wyżej wymienione ograniczenie może być nieco zaostrzone do czasu zapytania $O(n + m)$ jeśli użyjemy haszowania wrażliwego na lokalizację. Dokładniej, wybieramy $k := O(\frac{1}{\varepsilon^2})$ niezależne wektory gaussowskie $r_1, r_2, \ldots, r_k$ . Następnie mapujemy $\mathbb{R}^n$ do $\{0,1\}^k$ w następujący sposób: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$ . Następnie możemy oszacować kąt między dwoma wektorami w ramach błędu addytywnego $\varepsilon$ , obliczając $\ell_1$ -odległość na obrazie tego odwzorowania. W ten sposób możemy oszacować produkty kropkowe w ramach błędu addytywnego$\varepsilon \|x\| \|v_i\|$w czasie $O(\frac{1}{\varepsilon^2})$ .

Rozważ szczególny przypadek, w którym chcesz po prostu ustalić, czy wektor zapytania jest ortogonalny względem jakiegoś wektora w zbiorze wstępnie przetworzonym. (Oznacza to, że chcesz ustalić, czy , gdzie omawiane wektory mają współczynniki nieujemne.) Ten przypadek jest już bardzo interesujący.$\min_i \langle x, v_i \rangle = 0$

Załóżmy, że możesz odpowiadać na zapytania w czasie dla niektórych , przy użyciu wstępnego przetwarzania ( wielomianu stopnia nie powinna zależeć od i i ). δ > 0 m O ( 1 ) n O ( 1 ) m n $n^{O(1)} m^{1-\delta}$$\delta > 0$$m^{O(1)} n^{O(1)}$$m$$n$$\delta$

W artykule „Nowy algorytm dla optymalnej satysfakcji z 2 ograniczeń i jego implikacje” zauważyłem, że taka struktura danych faktycznie pozwoliłaby ci rozwiązać CNF-SAT w czasie przez pewien czas , gdzie jest liczbą zmiennych. To obaliłoby „hipotezę silnego czasu wykładniczego”, że k-SAT wymaga zasadniczo czasu na nieograniczony . α < 1 v 2 n$2^{\alpha v}$$\alpha < 1$$v$$2^n$$k$

Aby zobaczyć dlaczego, załóżmy, że czas wstępnego przetwarzania jest ograniczony przez . Rozważ wzór CNF ze zmiennymi i klauzulami . Podzieliliśmy zbiór zmiennych na dwie części, odpowiednio i o rozmiarze i . Wymień wszystkie możliwe przypisania do zmiennych w częściach (otrzymując odpowiednio i ). każde z tych częściowych przypisań z wektorem gdzie w F v n P 1 P 2 v ( 1 - 1 / ( 2 c ) ) v / ( 2 c ) 2 v ( 1 - 1 / ( 2 c ) ) 2 v / ( 2 c ) A i n w i w i [ j ] = 1 $(nm)^c$$F$$v$$n$$P_1$$P_2$$v(1-1/(2c))$$v/(2c)$$2^{v(1-1/(2c))}$$2^{v/(2c)}$$A_i$$n$$w_i$$w_i[j]=1$$j$klauzula nie jest spełniona przez . Mamy więc dwie listy wykładniczo wielu wektorów bitowych.A $F$$A_i$

Zauważ, że jest zadowalające, jeśli istnieje wektor z przydziału na i wektor z przydziału na taki że .w 1 p 1 w 2 P 2 ⟨ w 1 , w 2 ⟩ = $F$$w_1$$P_1$$w_2$$P_2$$\langle w_1, w_2 \rangle = 0$

Teraz pozwól i wstępnie przetworz założoną strukturę danych za pomocą wszystkich wektorów z części . Zakłada się, że zajmuje to czas . Uruchom algorytm zapytania dla wszystkich wektorów z przypisań w części . Z założenia przyjmuje to . Niech . P 2 n 2 v / 2 P 1 2 v ( 1 - 1 / ( 2 c ) ) ⋅ n O ( 1 ) m 1 - δ = n O ( 1 ) 2 v - δ v / ( 2 c ) α = 1 /$m=2^{v/(2c)}$$P_2$$n2^{v/2}$$P_1$$2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$$\alpha = 1 - \delta/(2c)$

Być może uda się uzyskać wydajne przetwarzanie wstępne i czas zapytania przy użyciu istniejących technik. Najbardziej znane algorytmy CNF-SAT tego nie wykluczają. (Dostają coś w rodzaju .) Ale aby obliczyć jest nieco silniejszy - w tej konfiguracji byłoby to jak rozwiązanie MAX CNF-SAT.$n^{O(1)} m^{1-1/(\log \log m)}$$2^{n-n/\log n}$$\min_i \langle x, v_i\rangle$

Oto jeden pomysł na dokładną odpowiedź, do której podejrzewam, że Chao Xu mógł nawiązać. Po pierwsze zauważ, że równie dobrze możemy znormalizować , jak wskazuje Chao. Teraz rozważ hiperpłaszczyznę normalną do kierunku . Celem jest znalezienie punktu najbliższego tej hiperpłaszczyźnie. W dualności odpowiada to zapytaniu o strzelanie promieniami w układzie hiperpłaszczyzn w celu znalezienia najbliższej płaszczyzny „powyżej” punktu zapytania. Ponieważ można to wstępnie przetworzyć, główną złożonością jest lokalizacja punktu, dlatego problem został zredukowany do złożoności wykonywania lokalizacji punktu w układzie hiperpłaszczyzn. Za pomocą sadzonek można to zrobić w czasie w przestrzeni .$x$$h$$x$$O(\log n)$$n^d$