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(n⋅f(n)))O(n1.8)O(n1.9)
Ω(n2/f(n))fΩ(n2/f2(n⋅f(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!