Problema 3SUM generalizado (k-SUM)?

29

O problema 3SUM tenta identificar 3 números inteiros de um conjunto de tamanho modo que .S n a + b + c = 0a,b,cSna+b+c=0

É conjeturado que não há solução melhor que quadrática, isto é, . Ou, de maneira diferente: .o ( n log ( n ) + n 2 )o(n2)o(nlog(n)+n2)

Então, eu queria saber se isso se aplicaria ao problema generalizado: Encontre números inteiros para em um conjunto de tamanho tal que . i [ 1 .. k ] S n i [ 1 .. k ] a i = 0aii[1..k]Sni[1..k]ai=0

Eu acho que você pode fazer isso em para (é trivial generalizar o algoritmo simples). Mas existem algoritmos melhores para outros valores de ?k 2 k = 3 ko(nlog(n)+nk1)k2k=3
k

bitmask
fonte
notícias recentes / papel na 3SUM que analisa a limites mais baixos em sua complexidade árvore de decisão
vzn

Respostas:

27

k -SUM pode ser resolvido mais rapidamente da seguinte maneira.

  • Para igual :k S k / 2 S x - x O ( n k / 2 log n ) calcule uma lista classificada de todas as somas de elementos de entrada. Verifique se contém algum número e sua negação . O algoritmo é executado no tempo .Sk/2SxxO(nk/2logn)

  • Para ímpar :k S ( k - 1 ) / 2 a S x - a - x x O ( n 2 ) O ( n ( k + 1 ) / 2 ) Calcule a lista classificada de todas as somas de elementos de entrada. Para cada elemento de entrada , verifique se contém e , para algum número . (O segundo passo é essencialmente o algoritmo de tempo para 3SUM.) O algoritmo é executado no tempo .S(k1)/2aSxaxxO(n2)O(n(k+1)/2)

Ambos os algoritmos são ótimos (exceto possivelmente para o fator de log quando é igual e maior que ) para qualquer constante em uma certa restrição fraca, mas natural, do modelo de computação da árvore de decisão linear. Para mais detalhes, consulte:k2k

JeffE
fonte
stackoverflow.com/a/14737071/511736 sugere o algoritmo O (n ^ 2) quando k = 4
Kowser em 21/08
1
Hashing é trapaça. O algoritmo descrito no StackOverflow é executado apenas no tempo O (n ^ 2) para entrada inteira, e somente com alta probabilidade, e somente se você usar uma função de hash aleatória apropriada. Os algoritmos na minha resposta funcionam no modelo de RAM real, são completamente determinísticos e os prazos são os piores casos. Você também pode cortar os fatores de log na configuração inteira usando "truques de bits", mas isso é meio chato.
JeffE
12

dnΩ(d)2o(n)

n

(1) Mihai Patrascu e Ryan Williams. Sobre a possibilidade de algoritmos SAT mais rápidos. Proc. 21º Simpósio ACM / SIAM sobre Algoritmos Discretos (SODA2010)

SamM
fonte
3

Aqui estão algumas observações simples.

k=1Θ(n)k=2Θ(nlogn)iiΘ(nlogn)k=nΘ(n) acumulando a matriz e verificando o resultado.

Para mais algumas referências, consulte a página The Open Problems Project para 3SUM .

Juho
fonte
-1

Veja http://arxiv.org/abs/1407.4640

Um novo algoritmo para resolver o problema rSUM Valerii Sopin

Abstrato:

Um algoritmo determinado é apresentado para resolver o problema rSUM para qualquer r natural com uma avaliação sub-quadrática da complexidade do tempo em alguns casos. Em termos de quantidade de memória utilizada, o algoritmo obtido também possui uma ordem sub-quadrática. A idéia do algoritmo obtido é baseada na consideração de números inteiros, mas em k∈N bits sucessivos desses números no sistema de numeração binária. É mostrado que, se uma soma de números inteiros for igual a zero, a soma dos números apresentados por quaisquer k bits sucessivos desses números deverá ser suficientemente "próxima" de zero. Isso torna possível descartar os números que, a fortiori, não estabelecem a solução.

É algo novo nesta edição.

user20970
fonte
1
Você poderia citar explicitamente os resultados do artigo que são relevantes para a pergunta? (Colar o resumo pode ser bom, se o artigo for relevante como um todo.) As postagens no SE devem ser mais do que apenas um link.
precisa saber é o seguinte
1
Sendo assim, esta resposta é um comentário (potencialmente útil), não uma resposta. Como tal, teria que conter algum conteúdo original, por exemplo, você descrevendo o algoritmo com suas próprias palavras. Você quer fazer isso? Posso converter sua resposta em um comentário, se não o fizer. (Estou ciente de que você não poderia comentar devido ao seu representante.)
Raphael
Isso não parece um papel credível. A afirmação "complexidade do tempo sub-quadrática em alguns casos" não é uma afirmação útil. A complexidade do tempo é, por definição, o pior caso de execução. A classificação das bolhas é executada em tempo linear em alguns casos, mas sua complexidade de tempo permanece quadrática.
DW