Versão multiplicativa do 3-SUM

O que se sabe sobre a complexidade temporal do seguinte problema, que chamamos de 3-MUL?

Dado um conjunto $S$ de números inteiros, existem elementos tais que ?$n$$a,b,c\in S$$ab=c$

Esse problema é semelhante ao problema da 3-SUM, que pergunta se existem três elementos modo que (ou equivalente ). 3-SUM é conjecturado para exigir aproximadamente o tempo quadrático em n . Existe uma conjectura semelhante para o 3-MUL? Especificamente, o 3-MUL é conhecido por ser 3-SUM difícil?$a,b,c\in S$$a+b+c=0$$a+b=c$$n$

Observe que a complexidade do tempo deve ser aplicada em um modelo "razoável" de computação. Por exemplo, poderíamos reduzir de 3-SUM em um conjunto para 3-MUL no conjunto , onde . Então uma solução para 3-MUL, , existe se e somente se . No entanto, esse aumento exponencial dos números é muito ruim em vários modelos, como o modelo de RAM, por exemplo.$S$$S'$$S'=\{2^x\mid x\in S\}$$2^a\cdot 2^b=2^c$$a+b=c$

Sua redução de SUM para 3 MUL funciona com uma pequena modificação padrão. Suponha que seus números inteiros originais estejam em { 1 , … , M }. Após a transformação x → 2 x, os novos números inteiros estão em { 2 , … , 2 M }. Vamos reduzir o alcance.$3$$3$$1,\ldots,M$$x\rightarrow 2^x$$2,\ldots,2^M$

Considere qualquer triplo de números inteiros no novo conjunto S ' . O número de divisores primos de qualquer diferente de zero a b - c é < 2 M . O número de tais triplos é n 3 . Portanto, o número de números primos q que dividem pelo menos um do um b - c não nulos números é, no máximo, 2 H N 3 .$a,b,c$$S'$$ab-c$$<2M$$n^3$$q$$ab-c$$2Mn^3$

Seja o conjunto dos primeiros 2 M ⋅ n 4 primos. O maior desses primos é de tamanho no máximo O ( M n 4 log M n ) . Escolher um primo aleatório p ∈ P . Com grande probabilidade p não dividirá qualquer um dos diferente de zero um b - c , portanto, podem representar cada um ∈ S ' pelo seu resíduo, modificação p , e se três MUL encontra algum um b = c em $P$$2M\cdot n^4$$O(Mn^4\log Mn)$$p\in P$$p$$ab-c$$a\in S'$$p$$3$$ab=c$ , Com alta probabilidade, será correto para ainstância 3 SUMoriginal. Reduzimos o intervalo dos números para { 0 , … , O ( M n 4 log M n ) }.$S'$$3$$0,\ldots, O(Mn^4\log Mn)$

(Esta é uma redução de tamanho padrão Você pode ser capaz de fazer melhor, considerando o fato de que os. são sempre diferenças de duas potências de 2 .)$ab-c$$2$

Você já tentou a redução onde M = max S - min S ? Os resultados são números reais, então você precisa arredondar para algum número de dígitos. Para garantir que os números sejam adicionados corretamente, apesar do arredondamento, talvez seja necessário adicionar um pouco de ruído aleatório.$S'=\{2^{x/M}|x\in S\}$$M=\max S− \min S$