La détection des progressions arithmétiques «doublement» est-elle difficile?

Ceci est inspiré d'une question d'entrevue .

On nous donne un tableau d'entiers et devons déterminer s'il existe des distincts tels que i < j < $a_1, \dots, a_n$$i \lt j \lt k$

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

c'est-à-dire que les séquences et sont toutes deux en progression arithmétique.{ i , j , k $\{a_i, a_j, a_k\}$$\{i,j,k\}$

Il existe un algorithme facile pour cela, mais trouver un algorithme sub-quadratique semble difficile à atteindre.$O(n^2)$

Est-ce un problème connu? Pouvons-nous en prouver la dureté 3SUM? (ou peut-être fournir un algorithme sub-quadratique?)

Si vous le souhaitez, vous pouvez supposer et que pour une constante connue . (Dans le problème de l'entretien, ).a r + 1 - a r ≤ K K > 2 K = $0 \lt a_1 \lt a_2 \lt ... \lt a_n$$a_{r+1} - a_{r} \le K$$K > 2$$K = 9$

Ceci est un problème ouvert.

Une forme faible de dureté 3SUM pourrait être prouvée en adaptant un résultat du document STOC 2010 de Mihai Pătrașcu " Vers des limites inférieures polynomiales pour les problèmes dynamiques ". Tout d'abord, permettez-moi de définir une séquence de problèmes étroitement liés. L'entrée de chaque problème est un tableau trié d'entiers distincts.$A[1..n]$

• 3SUM: Existe-t-il des indices distincts tels que ?A [ i ] + A [ j ] = A [ k $i,j,k$$A[i] + A[j] = A[k]$

• Convolution3SUM: Y a-t-il des indices tels que ?A [ i ] + A [ j ] = A [ i + j $i<j$$A[i] + A[j] = A[i+j]$

• Moyenne: existe-t-il des indices distincts tels que ?A [ i ] + A [ j ] = 2 A [ k $i,j,k$$A[i] + A[j] = 2 A[k]$

• ConvolutionAverage: Y a-t-il des indices tels que ? (C'est le problème que vous posez.)A [ i ] + A [ j ] = 2 A [ ( i + j ) / 2 $i<j$$A[i] + A[j] = 2A[(i+j)/2]$

Dans ma thèse de doctorat, j'ai prouvé que ces quatre problèmes nécessitent un temps dans un modèle d'arbre décisionnel de calcul qui ne permet que des requêtes de la forme "Is positif, négatif ou zéro? ", où sont des nombres réels (qui ne dépendent pas de l'entrée). En particulier, tout algorithme 3SUM de ce modèle doit poser la question " plus grand, plus petit ou égal à ?" au moins fois. Cette borne inférieure n'exclut pas les algorithmes sous-quadratiques dans un modèle de calcul plus général - en effet, il est possible de réduire certains facteurs de logα A [ i ] + β A [ j ] + γ A [ k ] + δ α , β , γ , δ A [ i ] + A [ j ] A [ k ] Ω ( n 2$\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)$dans divers modèles de RAM entiers. Mais personne ne sait quel type de modèle plus général aiderait de manière plus significative.

En utilisant une réduction minutieuse du hachage, Pǎtrașcu a prouvé que si 3SUM nécessite temps prévu, pour toute fonction , alors Convolution3SUM nécessite temps prévu. Ainsi, il est raisonnable de dire que Convolution3SUM est "faiblement dur 3SUM". Par exemple, si Convolution3SUM peut être résolu en temps , alors 3SUM peut être résolu en temps .$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$$O(n^{1.8})$$O(n^{1.9})$

Je n'ai pas approfondi les détails, mais je parierais qu'un argument parallèle implique que si la moyenne nécessite temps prévu, pour toute fonction , alors ConvolutionAverage nécessite heure prévue. En d'autres termes, ConvolutionAverage est "faiblement moyen-dur".$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$

Malheureusement, on ne sait pas si la moyenne est (même faiblement) 3SUM-difficile! Je soupçonne que la moyenne n'est en fait pas dure de 3SUM, ne serait-ce que parce que la borne inférieure pour Average est considérablement plus difficile à prouver que la borne inférieure pour 3SUM .$\Omega(n^2)$$\Omega(n^2)$

Vous demandez aussi sur le cas particulier où les éléments de tableau adjacents diffèrent de moins de quelques - uns fixe entier . Pour 3SUM et Average, cette variante peut être résolue en temps utilisant les transformées de Fourier rapides comme suit. (Cette observation est due à Raimund Seidel.) $K$$O(n \log n)$

Construire un vecteur de bits , où si et seulement si le nombre entier apparaît dans le tableau d'entrée . Calculez la convolution de avec elle-même en temps aide des FFT. Le tableau résultant a une valeur non nulle en ème position si et seulement si une paire d'éléments dans somme à . Ainsi, nous pouvons extraire une liste triée de sommes de la convolution en temps . À partir d'ici, il est facile de résoudre la moyenne ou 3SUM en temps .B [ i ] = 1 A [ 1 ] + i A B O ( K n log K n ) = O ( n log n ) j A 2 A [ 1 ] + j A [ i ] + A [ j ] O ( n ) O ( n $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)$

Mais je ne connais pas une astuce similaire pour Convolution3SUM ou ConvolutionAverage!