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ćcoś , co jest w pewnym sensie zbliżone do dla większości (przynajmniej jeśli normy i są małe).
UPD Wyżej wymienione ograniczenie może być nieco zaostrzone do czasu zapytania jeśli użyjemy haszowania wrażliwego na lokalizację. Dokładniej, wybieramy niezależne wektory gaussowskie . Następnie mapujemy do w następujący sposób: . Następnie możemy oszacować kąt między dwoma wektorami w ramach błędu addytywnego , obliczając -odległość na obrazie tego odwzorowania. W ten sposób możemy oszacować produkty kropkowe w ramach błędu addytywnegow czasie .
Odpowiedzi:
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.mini⟨x,vi⟩=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 δnO(1)m1−δ δ>0 mO(1)nO(1) m n δ
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 k2αv α<1 v 2n 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 j(nm)c F v n P1 P2 v(1−1/(2c)) v/(2c) 2v(1−1/(2c)) 2v/(2c) Ai n wi wi[j]=1 j klauzula nie jest spełniona przez . Mamy więc dwie listy wykładniczo wielu wektorów bitowych.A iF Ai
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 ⟩ = 0F w1 P1 w2 P2 ⟨w1,w2⟩=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=2v/(2c) P2 n2v/2 P1 2v(1−1/(2c))⋅nO(1)m1−δ=nO(1)2v−δv/(2c) α=1−δ/(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.nO(1)m1−1/(loglogm) 2n−n/logn mini⟨x,vi⟩
źródło
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(logn) nd
źródło