Ist das Erkennen von "doppelt" arithmetischen Verläufen 3SUM-hard?

Dies wird durch eine Interviewfrage inspiriert .

Wir erhalten ein Array von ganzen Zahlen und müssen bestimmen, ob es verschiedene i < j < k gibt, so dass$a_1, \dots, a_n$$i \lt j \lt k$

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

dh die Folgen und { i , j , k } sind beide in arithmetischer Folge.$\{a_i, a_j, a_k\}$$\{i,j,k\}$

Hierfür gibt es einen einfachen -Algorithmus, die Suche nach einem subquadratischen Algorithmus ist jedoch schwierig.$O(n^2)$

Ist das ein bekanntes Problem? Können wir 3SUM-Härte davon nachweisen? (oder vielleicht einen subquadratischen Algorithmus bereitstellen?)

Wenn Sie möchten, können Sie annehmen . . . < A n und a r + 1 - a r ≤ K für einige bekannte Konstante K > 2 . (Im Interviewproblem ist K = 9 ).$0 \lt a_1 \lt a_2 \lt ... \lt a_n$$a_{r+1} - a_{r} \le K$$K > 2$$K = 9$

Dies ist ein offenes Problem.

Möglicherweise konnte eine schwache Form der 3SUM-Härte nachgewiesen werden, indem ein Ergebnis aus Mihai Pătrașcus STOC 2010-Arbeit " Towards Polynomial Lower Bounds for Dynamic Problems " angepasst wurde . Lassen Sie mich zunächst eine Abfolge eng verwandter Probleme definieren. Die Eingabe für jedes Problem ist ein sortiertes Array unterschiedlicher Ganzzahlen.$A[1..n]$

• 3SUM: Gibt es verschiedene Indizes so dass A [ i ] + A [ j ] = A [ k ] ?$i,j,k$$A[i] + A[j] = A[k]$

• Convolution3SUM: Gibt es Indizes so dass A [ i ] $i<j$ ?$A[i] + A[j] = A[i+j]$

• Mittelwert: Gibt es verschiedene Indizes so dass A [ i ] $i,j,k$ ?$A[i] + A[j] = 2 A[k]$

• ConvolutionAverage: Gibt es Indizes , so dass A [ i ] + A [ j ] = 2 A [ ( i + j ) / 2 ] ? (Dies ist das Problem, nach dem Sie fragen.)$i<j$$A[i] + A[j] = 2A[(i+j)/2]$

In meiner Doktorarbeit habe ich bewiesen, dass alle vier dieser Probleme -Zeit in einem Entscheidungsbaum-Berechnungsmodell erfordern , das nur Abfragen der Form "Ist α A [ i ] + β A [ j ] + γ " zulässt A [ k ] + δ positiv, negativ oder Null? ", Wobei α , β , γ , δ reelle Zahlen sind (die nicht von der Eingabe abhängen). Insbesondere muss jeder 3SUM-Algorithmus in diesem Modell die Frage "Ist A [ $\Omega(n^2)$$\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$$\alpha,\beta,\gamma,\delta$ größer, kleiner oder gleich A [ k ] ? "Mindestens Ω ( n 2 ) mal. Diese Untergrenze schließt subquadratische Algorithmen in einem allgemeineren Rechenmodell nicht aus - tatsächlich ist es das auch möglicheinige LogFaktoren abrasierenin verschiedenen integerRAMModellen. Aber niemand weißwas für allgemeinere Modell deutlich mehr helfen würde.$A[i] + A[j]$$A[k]$$\Omega(n^2)$

$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$ expected time. Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard". For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$

Ich habe die Details nicht durchgearbeitet, aber ich wette, dass ein paralleles Argument impliziert, dass, wenn der Durchschnitt erfordert$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$ expected time. In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard! I suspect that Average is actually not 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is considerably harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.

You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$. For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows. (This observation is due to Raimund Seidel.)

Build a bit vector $B[0..Kn]$, where $B[i]=1$ if and only if the integer $A[1]+i$ appears in the input array $A$. Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs. The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A[1] + j$. Thus, we can extract a sorted list of sums $A[i]+A[j]$ from the convolution in $O(n)$ time. From here, it's easy to solve Average or 3SUM in $O(n)$ time.

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!