Versión multiplicativa de 3-SUM

¿Qué se sabe sobre la complejidad temporal del siguiente problema, que llamamos 3-MUL?

Dado un conjunto de n enteros, ¿hay elementos a, b, c \ en S tales que ab = c ?n a , b , c ∈ S a b = $S$$n$$a,b,c\in S$$ab=c$

Este problema es similar al problema 3-SUM, que pregunta si hay tres elementos modo que (o equivalente ). Se conjetura que 3-SUMA requiere un tiempo aproximadamente cuadrático en . ¿Hay una conjetura similar para 3-MUL? Específicamente, ¿se sabe que 3-MUL es difícil de 3-SUM?a + b + c = 0 a + b = c $a,b,c\in S$$a+b+c=0$$a+b=c$$n$

Tenga en cuenta que la complejidad del tiempo debe aplicarse en un modelo de cálculo "razonable". Por ejemplo, podríamos reducir de 3-SUM en un conjunto a 3-MUL en el conjunto , donde . Entonces , existe una solución para 3-MUL, , si y solo si . Sin embargo, este aumento exponencial de los números se escala muy mal con varios modelos, como el modelo RAM, por ejemplo.S ′ S ′ = { 2 x ∣ x ∈ S } 2 a ⋅ 2 b = 2 c a + b = $S$$S'$$S'=\{2^x\mid x\in S\}$$2^a\cdot 2^b=2^c$$a+b=c$

Su reducción de SUM a 3 MUL funciona con una modificación estándar menor. Suponga que sus enteros originales estaban en { 1 , ... , M }. Después de la transformación x → 2 x, los nuevos enteros están en { 2 , ... , 2 M }. Reduciremos el alcance.$3$$3$$1,\ldots,M$$x\rightarrow 2^x$$2,\ldots,2^M$

Considere cualquier triple de enteros en el nuevo conjunto S ' . El número de divisores primos de cualquier distinto de cero un b - c es < 2 M . El número de tales triples es n 3 . Por lo tanto el número de primos q que divide al menos una de la una b - c no nulos números es como máximo de 2 M n 3 .$a,b,c$$S'$$ab-c$$<2M$$n^3$$q$$ab-c$$2Mn^3$

Sea el conjunto de los primeros 2 M ⋅ n 4 primos. El primo más grande es de tamaño como máximo O ( M n 4 log M n ) . Escoja un primer aleatorio p ∈ P . Con alta probabilidad, p no dividirá ninguno de los no a cero a b - c , por lo que podemos representar a cada a ∈ S ′ por su residuo, mod p , y si 3 MUL encuentra algo a b = c en $P$$2M\cdot n^4$$O(Mn^4\log Mn)$$p\in P$$p$$ab-c$$a\in S'$$p$$3$$ab=c$ , Con alta probabilidad será correcta para lainstanciaoriginal de 3 SUM. Hemos reducido el rango de los números a { 0 , ... , O ( M n 4 log M n ) }.$S'$$3$$0,\ldots, O(Mn^4\log Mn)$

(Esta es una reducción de tamaño estándar Usted puede ser capaz de hacerlo mejor, considerando el hecho de que los. son siempre las diferencias de dos potencias de 2 ).$ab-c$$2$

¿Has probado la reducción donde M = max S - min S ? Los resultados son números reales, por lo que tendría que redondear a una cierta cantidad de dígitos. Para garantizar que los números se sumen correctamente a pesar del redondeo, es posible que deba agregar un poco de ruido aleatorio.$S'=\{2^{x/M}|x\in S\}$$M=\max S− \min S$