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

20

Isso é inspirado em uma pergunta da entrevista .

Recebemos uma matriz de números inteiros a1,,an e precisamos determinar se existem distintos, de modo quei<j<k

  • akaj=ajai
  • kj=ji

isto é, as seqüências e estão ambas em progressão aritmética.{ i , j , k }{ai,aj,ak}{i,j,k}

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

É 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<a1<a2<...<anar+1arKK>2K=9

Knoothe
fonte

Respostas:

12

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,kA[i]+A[j]=A[k]

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

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

  • ConvolutionAverage: Existem índices tais que A [ i ] + A [ j ] = 2 A [ ( i + j ) / 2 ] ? (Esse é o problema que você está perguntando.)i<jA[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 [ iΩ(n2)αA[i]+βA[j]+γA[k]+δα,β,γ,δ 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]Ω(n2)

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 (Ω(n2/f(n))fΩ(n2/f2(nf(n)))O(n1.8) tempo.O(n1.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".Ω(n2/f(n))fΩ(n2/f2(nf(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Ω(n2) é consideravelmente mais difícil de provar do que a limite inferior para 3SUMΩ(n2) .


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.) KO(nlogn)

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 jB[0..Kn]B[i]=1A[1]+iABO(KnlogKn)=O(nlogn)jth 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.A2A[1]+jA[i]+A[j]O(n)O(n)

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

JeffE
fonte