¿Detectar progresiones aritméticas "doblemente" es 3SUM-hard?

20

Esto está inspirado en una pregunta de entrevista .

Se nos da una matriz de enteros y tenemos que determinar si hay distintos manera quea1,,ani<j<k

  • akaj=ajai
  • kj=ji

es decir, las secuencias y están ambas en progresión aritmética.{ai,aj,ak}{i,j,k}

Hay un algoritmo fácil para esto, pero parece difícil encontrar un algoritmo subcuadrático.O(n2)

¿Es este un problema conocido? ¿Podemos demostrar la dureza 3SUM de esto? (o tal vez proporcionar un algoritmo sub-cuadrático?)

Si lo desea, puede suponer y que para alguna constante conocida . (En el problema de la entrevista, ).0<a1<a2<...<anar+1arKK>2K=9

Knoothe
fuente

Respuestas:

12

Este es un problema abierto.

Posiblemente se podría probar alguna forma débil de dureza 3SUM adaptando un resultado del documento STOC 2010 de Mihai Pătrașcu " Hacia límites polinómicos inferiores para problemas dinámicos ". Primero, permítanme definir una secuencia de problemas estrechamente relacionados. La entrada a cada problema es una matriz ordenada de enteros distintos.A[1..n]

  • 3SUM: ¿Hay índices distintos tales que ?i,j,kA[i]+A[j]=A[k]

  • Convolución3SUM: ¿Hay índices tales que ?i<jA[i]+A[j]=A[i+j]

  • Promedio: ¿Hay índices distintos manera que ?i,j,kA[i]+A[j]=2A[k]

  • Promedio de convolución: ¿Hay índices tales que ? (Este es el problema que estás preguntando).i<jA[i]+A[j]=2A[(i+j)/2]

En mi tesis doctoral, probé que los cuatro problemas requieren tiempo en un modelo de cálculo de árbol de decisión que solo permite consultas de la forma "Is positivo, negativo o cero? ", dondeΩ(n2)αA[i]+βA[j]+γA[k]+δα,β,γ,δA[i]+A[j]A[k]Ω(n2)veces. Ese límite inferior no excluye los algoritmos subcuadráticos en un modelo de cómputo más general; de hecho, es posible eliminar algunos factores de registro en varios modelos de RAM entera. Pero nadie sabe qué tipo de modelo más general ayudaría de manera más significativa.

Ω(n2/f(n))fΩ(n2/f2(nf(n)))O(n1.8)O(n1.9)

Ω(n2/f(n))fΩ(n2/f2(nf(n)))

Ω(n2)Ω(n2)


KO(nlogn)

B[0..Kn]B[i]=1A[1]+iABO(KnlogKn)=O(nlogn)jA2A[1]+jA[i]+A[j]O(n)O(n) tiempo.

¡Pero no conozco un truco similar para Convolution3SUM o ConvolutionAverage!

JeffE
fuente