Czy wykrywanie „podwójnie” postępów arytmetycznych 3SUM jest trudne?

Jest to inspirowane pytaniem podczas wywiadu .

tablicę liczb całkowitych i musimy ustalić, czy istnieją wyraźne i \ lt j \ ltk takie, że$a_1, \dots, a_n$$i \lt j \lt k$

• $a_k - a_j = a_j - a_i$
• $k - j = j - i$

tj. sekwencje $\{a_i, a_j, a_k\}$ i $\{i,j,k\}$ są w postępie arytmetycznym.

Jest do tego łatwy algorytm $O(n^2)$ , ale znalezienie algorytmu subkwadratowego wydaje się nieuchwytne.

Czy to znany problem? Czy możemy udowodnić twardość 3SUM tego? (a może podać algorytm subkwadratowy?)

Jeśli chcesz, możesz założyć $0 \lt a_1 \lt a_2 \lt ... \lt a_n$ i że $a_{r+1} - a_{r} \le K$ dla niektórych znanych stałych $K > 2$ . (W problemie z wywiadem $K = 9$ ).

To jest otwarty problem.

Być może można udowodnić pewną słabą formę twardości 3SUM, dostosowując wynik z dokumentu STOC 2010 Mihai Pătrașcu „ W kierunku dolnych granic wielomianu dla problemów dynamicznych ”. Po pierwsze, pozwól mi zdefiniować sekwencję ściśle powiązanych problemów. Dane wejściowe do każdego problemu stanowią posortowana tablica różnych liczb całkowitych.$A[1..n]$

• 3SUMA: Czy istnieją odrębne wskaźniki takie, że ?$i,j,k$$A[i] + A[j] = A[k]$

• Convolution3SUM: Czy istnieją wskaźniki takie, że ?$i<j$$A[i] + A[j] = A[i+j]$

• Średnia: Czy istnieją odrębne wskaźniki takie, że ?$i,j,k$$A[i] + A[j] = 2 A[k]$

• ConvolutionA Average: Czy istnieją wskaźniki takie, że ? (O to pytasz.)$i<j$$A[i] + A[j] = 2A[(i+j)/2]$

W mojej pracy doktorskiej udowodniłem, że wszystkie cztery z tych problemów wymagają czasu w modelu obliczeń drzewa decyzyjnego, który dopuszcza tylko zapytania o postaci „Is dodatnia, ujemna lub zero? ”, gdzie są liczbami rzeczywistymi (które nie zależą od danych wejściowych). W szczególności dowolny algorytm 3SUM w tym modelu musi zadać pytanie „Czy większy, mniejszy lub równy ?” co najmniej razy. Ta dolna granica nie wyklucza algorytmów subkwadratowych w bardziej ogólnym modelu obliczeń - w rzeczywistości możliwe jest zmniejszenie niektórych czynników logarytmicznych$\Omega(n^2)$$\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$$\alpha,\beta,\gamma,\delta$$A[i] + A[j]$$A[k]$$\Omega(n^2)$w różnych całkowitych modelach pamięci RAM. Ale nikt nie wie, jaki rodzaj bardziej ogólnego modelu pomógłby bardziej.

Używając starannej redukcji haszowania, Pǎtrașcu udowodnił, że jeśli 3SUM wymaga oczekiwanego czasu dla dowolnej funkcji , to Convolution3SUM wymaga oczekiwany czas. Dlatego rozsądne jest stwierdzenie, że Convolution3SUM jest „słabo twardy 3SUM”. Na przykład, jeśli Convolution3SUM można rozwiązać w czasie , wówczas 3SUM można rozwiązać w czasie .$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$$O(n^{1.8})$$O(n^{1.9})$

Nie oparłem się na szczegółach, ale założę się, że równoległy argument sugeruje, że jeśli Średnia wymaga oczekiwanego czasu, dla dowolnej funkcji , to ConvolutionAternal wymaga oczekiwany czas. Innymi słowy, ConvolutionAverage jest „słabo średnio-trudny”.$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$

Niestety nie wiadomo, czy średnia jest (nawet słabo) 3SUM-trudna! Podejrzewam, że średnia jest faktycznie nie 3SUM twardy, choćby dlatego, że dolna granica dla przeciętnych jest znacznie trudniejsze do udowodnienia niż dolna granica dla 3SUM .$\Omega(n^2)$$\Omega(n^2)$

Również zapytać o szczególnym przypadku, w którym sąsiednie elementy tablicy różnią się o mniej niż niektóre stałe całkowita . Dla 3SUM i średniej wariant ten można rozwiązać w czasie przy użyciu szybkich transformacji Fouriera w następujący sposób. (Ta obserwacja wynika z Raimunda Seidla.) $K$$O(n \log n)$

Budowanie bitowy wektor , gdzie , wtedy i tylko wtedy, gdy liczba całkowita pojawia się w macierzy wejścia . Obliczania splotu z ze sobą w czas za pomocą FFT. Wynikowa tablica ma niezerową wartość w tej pozycji wtedy i tylko wtedy, gdy jakaś para elementów w sumie do . Możemy więc wyodrębnić posortowaną listę sum ze splotu w czasie . Stąd łatwo jest rozwiązać średnią lub 3 SUMY w czasie .$B[0..Kn]$$B[i]=1$$A[1]+i$$A$$B$$O(Kn\log Kn) = O(n\log n)$$j$$A$$2A[1] + j$$A[i]+A[j]$$O(n)$$O(n)$

Ale nie znam podobnej sztuczki dla Convolution3SUM lub ConvolutionA Average!