Generalised 3SUM (k-SUM) problem?

Le problème 3SUM essaie d'identifier 3 entiers$a,b,c$$S$$n$$a + b + c = 0$

On suppose qu'il n'y a pas de meilleure solution que quadratique, c'est-à-dire $\mathcal{o}(n^2)$$\mathcal{o}(n \log(n) + n^2)$

Je me demandais donc si cela s'appliquerait au problème généralisé: trouver des entiers $a_i$$i \in [1..k]$$S$$n$$\sum_{i \in [1..k]} a_i = 0$

I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$$k \geq 2$$k=3$
$k$

$k$

• Même pour $k$$S$$k/2$$S$$x$$-x$$O(n^{k/2}\log n)$

• Pour impair $k$$S$$(k-1)/2$$a$$S$$x$$-a-x$$x$$O(n^2)$$O(n^{(k+1)/2})$

Les deux algorithmes sont optimaux (sauf éventuellement pour le facteur logarithmique lorsque $k$$2$$k$

• Nir Ailon et Bernard Chazelle. Limites inférieures pour les tests de dégénérescence linéaire . JACM 2005.

• Jeff Erickson. Limites inférieures pour les problèmes de satisfiabilité linéaire . CJTCS 1999.

$d$-SUM nécessite du temps $n^{\Omega(d)}$ sauf si k-SAT peut être résolu en $2^{o(n)}$temps pour toute constante k. Cela a été montré dans un article de Mihai Patrascu et Ryan Williams (1).

En d'autres termes, en supposant l' hypothèse de temps exponentielle , votre algorithme est optimal jusqu'à un facteur constant dans l'exposant (un facteur polynomial dans$n$)

(1) Mihai Patrascu et Ryan Williams. Sur la possibilité d'algorithmes SAT plus rapides. Proc. 21e Symposium ACM / SIAM sur les algorithmes discrets (SODA2010)

Voici quelques observations simples.

Pour $k=1$, vous pouvez le faire en $\Theta(n)$temps en balayant le tableau pour un zéro. Pour$k=2$, vous pouvez le faire sans hachage $\Theta(n \log n)$temps. Triez la baie puis scannez-la. Pour chaque élément$i$ faire une recherche binaire pour $-i$. Il en résulte une complexité totale de$\Theta(n \log n)$. Pour le cas$k=n$ vous pouvez le faire en $\Theta(n)$ temps en accumulant le tableau et en vérifiant le résultat.

Pour plus de références, consultez la page du projet Problèmes ouverts pour 3SUM .

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

Un nouvel algorithme pour résoudre le problème rSUM Valerii Sopin

Abstrait:

Un algorithme déterminé est présenté pour résoudre le problème rSUM pour tout r naturel avec une évaluation sub-quadratique de la complexité temporelle dans certains cas. En termes de quantité de mémoire utilisée, l'algorithme obtenu a également un ordre sub-quadratique. L'idée de l'algorithme obtenu est basée non pas sur les nombres entiers, mais sur k∈N bits successifs de ces nombres dans le système de numération binaire. On montre que si une somme de nombres entiers est égale à zéro, alors la somme de nombres présentée par tout k bits successifs de ces nombres doit être suffisamment "proche" de zéro. Cela permet d'écarter les chiffres qui, a fortiori, n'établissent pas la solution.

C'est quelque chose de nouveau dans ce numéro.