Versão multiplicativa do 3-SUM

22

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 ?na,b,cSab=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,cSa+b+c=0a+b=cn

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.SSS={2xxS}2a2b=2ca+b=c

Markus Jalsenius
fonte
Sua redução mostra que 3-MULT é difícil de 3-SUM se os números de entrada puderem ser expressos usando notação exponencial (também conhecida como científica).
Warren Schudy
4
Qualquer algoritmo para o 3-SUM que se baseia unicamente no fato de que a adição é um grupo pode ser convertido em um algoritmo para o 3-MULT e vice-versa. Qualquer algoritmo que separasse os dois precisaria, portanto, fazer algo incomum com os números.
Warren Schudy
1
para ser terrivelmente pedante, talvez precisemos apenas de um semigrupo.
Suresh Venkat

Respostas:

11

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.331,,Mx2x2,,2M

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,cSabc<2Mn3qabc2Mn3

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 SP2Mn4O(Mn4logMn)pPpabcaSp3ab=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 ) }.S30,,O(Mn4logMn)

(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 .)abc2

virgi
fonte
1
Você não reduziu a 3MUL mod um prime ao invés de 3MUL? Pode ser que mas a b c . ab=c(mod()p)abc
Warren Schudy 20/10/10
1
Sim, como está, é uma redução para o 3MUL mod p. Bom ponto.
Virgen #
Esta é uma abordagem muito interessante. No entanto, estamos particularmente interessados ​​em uma redução determinística de 3-SUM para 3-MUL. Seria possível derandomizar a técnica de redução de tamanho?
Markus Jalsenius
3

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={2x/M|xS}M=maxSminS

Warren Schudy
fonte
Ops, ruído aleatório não parece suficiente para corrigir o erro de arredondamento. No entanto, estas ideias não parecem promissores para reduzir a outra maneira de mostrar 3-MULT mais difícil do que 3-SUM é, desde eg . (x+1)+y=x+y+1
Warren Schudy
1
A equação não parece correta (tente x e y = 2.1). Você poderia esclarecer o que quis dizer?
Raphael