Detectar progressões aritméticas “duplamente” 3SUM é difícil?

Isso é inspirado em uma pergunta da entrevista .

Recebemos uma matriz de números inteiros $a_1, \dots, a_n$ e precisamos determinar se existem distintos, de modo que$i \lt j \lt k$

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

isto é, as seqüências e estão ambas em progressão aritmética.{ i , j , k $\{a_i, a_j, a_k\}$$\{i,j,k\}$

Existe um algoritmo fácil para isso, mas encontrar um algoritmo sub-quadrático parece ilusório.$O(n^2)$

É um problema conhecido? Podemos provar a dureza 3SUM disso? (ou talvez fornecer um algoritmo sub-quadrático?)

Se desejar, você pode assumir e que para alguma constante conhecida . (No problema da entrevista, ).$0 \lt a_1 \lt a_2 \lt ... \lt a_n$$a_{r+1} - a_{r} \le K$$K > 2$$K = 9$

Este é um problema em aberto.

Possivelmente, alguma forma fraca de dureza 3SUM pode ser comprovada adaptando um resultado do artigo STOC 2010 de Mihai Pătrașcu " Em direção a limites inferiores polinomiais para problemas dinâmicos ". Primeiro, deixe-me definir uma sequência de problemas intimamente relacionados. A entrada para cada problema é uma matriz classificada de números inteiros distintos.$A[1..n]$

• 3SUM: Existem índices distintos tais que A [ i ] + A [ j ] = A [ k ] ?$i,j,k$$A[i] + A[j] = A[k]$

• Convolution3SUM: Existem índices tais que A [ i ] + A [ j ] = A [ i + j ] ?$i<j$$A[i] + A[j] = A[i+j]$

• Média: Existem índices distintos tais que A [ i ] + A [ j ] = 2 A [ k ] ?$i,j,k$$A[i] + A[j] = 2 A[k]$

• ConvolutionAverage: Existem índices tais que A [ i ] + A [ j ] = 2 A [ ( i + j ) / 2 ] ? (Esse é o problema que você está perguntando.)$i<j$$A[i] + A[j] = 2A[(i+j)/2]$

Na minha tese de doutoramento, eu provei que todos os quatro destes problemas requerem tempo em um modelo de árvore de decisão de computação que permite apenas consultas da forma "é α A [ i ] + β A [ j ] + γ A [ k ] + δ positivo, negativo ou zero? ", Onde α , β , γ , δ são números reais (que não dependem da entrada). Em particular, qualquer algoritmo 3SUM neste modelo deve fazer a pergunta "É A [ $\Omega(n^2)$$\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$$\alpha,\beta,\gamma,\delta$ maior, menor ou igual a A [ k ] ? "Pelo menos Ω ( n 2 ) vezes. Esse limite inferior não descarta algoritmos subquadráticos em um modelo mais geral de computação - de fato, é É possívelreduzir alguns fatores de logem vários modelos de RAM inteiros, mas ninguém sabe que tipo de modelo mais geral ajudaria mais significativamente.$A[i] + A[j]$$A[k]$$\Omega(n^2)$

Usando uma cuidadosa redução de hash, Pǎtrașcu provou que se o 3SUM requer tempo esperado, para qualquer função f , o Convolution3SUM exige Ω ( n 2 / f 2 ( n ⋅ f ( n ) ) ) esperado Tempo. Portanto, é razoável dizer que o Convolution3SUM é "fracamente difícil no 3SUM". Por exemplo, se Convolution3SUM puder ser resolvido em O ( n 1,8 ) , então 3SUM poderá ser resolvido em O $\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$$O(n^{1.8})$ tempo.$O(n^{1.9})$

Eu não me baseiei nos detalhes, mas eu apostaria que um argumento paralelo implica que se a Média exigir tempo esperado, para qualquer função f , então ConvolutionAverage exige Ω ( n 2 / f 2 ( n ⋅ f ( n ) ) ) tempo esperado. Em outras palavras, ConvolutionAverage é "fracamente médio-difícil".$\Omega(n^2/f(n))$$f$$\Omega(n^2/f^2(n\cdot f(n)))$

Infelizmente, não se sabe se a média é (mesmo que fraca) 3SUM-difícil! Eu suspeito que média é, na verdade, não 3SUM-duro, mesmo porque a limite inferior para média$\Omega(n^2)$ é consideravelmente mais difícil de provar do que a limite inferior para 3SUM$\Omega(n^2)$ .

Também perguntar sobre o caso especial onde os elementos de matriz adjacentes diferem em menos do que alguns fixo inteiro . Para 3SUM e Average, essa variante pode ser resolvida em O ( n log n ) usando as transformações Fast Fourier da seguinte maneira. (Esta observação é devida a Raimund Seidel.) $K$$O(n \log n)$

Construir um vector de bits , onde B [ i ] = 1 , se e apenas se o número inteiro Um [ 1 ] + i aparece na matriz de entrada A . Calcule a convolução de B consigo no tempo O ( K n log K n ) = O ( n log n ) usando FFTs. A matriz resultante tem um valor diferente de zero no $B[0..Kn]$$B[i]=1$$A[1]+i$$A$$B$$O(Kn\log Kn) = O(n\log n)$$j$th posição se e somente se algum par de elementos em somar 2 A [ 1 ] + j . Assim, podemos extrair uma lista classificada das somas A [ i ] + A [ j ] da convolução no tempo O ( n ) . A partir daqui, é fácil resolver Média ou 3SUM em O ( n ) tempo.$A$$2A[1] + j$$A[i]+A[j]$$O(n)$$O(n)$

Mas não conheço um truque semelhante para Convolution3SUM ou ConvolutionAverage!