Version multiplicative de 3-SUM

22

Que sait-on de la complexité temporelle du problème suivant, que nous appelons 3-MUL?

Étant donné un ensemble de entiers, y a-t-il des éléments tels que ?Sna,b,cSab=c

Ce problème est similaire au problème 3-SUM, qui demande s'il y a trois éléments tels que (ou de manière équivalente ). 3-SUM est supposé nécessiter un temps à peu près quadratique en . Existe-t-il une conjecture similaire pour le 3-MUL? Plus précisément, le 3-MUL est-il connu pour être 3-SUM difficile?a,b,cSa+b+c=0a+b=cn

Notez que la complexité temporelle doit s'appliquer dans un modèle de calcul "raisonnable". Par exemple, nous pourrions réduire de 3-SUM sur un ensemble à 3-MUL sur l'ensemble , où . Alors une solution à 3-MUL, , existe si et seulement si . Cependant, cette explosion exponentielle des nombres évolue très mal avec différents modèles, comme le modèle RAM par exemple.SSS={2xxS}2a2b=2ca+b=c

Markus Jalsenius
la source
Votre réduction montre que 3-MULT est difficile à 3-SUM si les nombres d'entrée peuvent être exprimés en utilisant une notation exponentielle (aka scientifique).
Warren Schudy
4
Tout algorithme pour 3-SUM qui repose uniquement sur le fait que l'addition est un groupe peut être traduit en un algorithme pour 3-MULT, et vice versa. Tout algorithme séparant les deux devrait donc faire quelque chose d'inhabituel avec les nombres.
Warren Schudy
1
pour être horriblement pédant, nous pourrions avoir seulement besoin d'un semi-groupe.
Suresh Venkat

Réponses:

11

Votre réduction de SUM à 3 MUL fonctionne avec une modification standard mineure. Supposons que vos entiers d'origine étaient dans { 1 , , M }. Après la transformation x 2 x les nouveaux entiers sont dans { 2 , , 2 M }. Nous allons réduire la portée.331,,Mx2x2,,2M

Considérons tout triple d'entiers dans le nouvel ensemble S . Le nombre de diviseurs premiers de toute valeur non nulle a b - c est < 2 M . Le nombre de ces triplets est n 3 . Ainsi , le nombre des nombres premiers q qui divisent au moins l' un des a b - c nombres non nuls est au plus de 2 M n 3 .a,b,cSabc<2Mn3qabc2Mn3

Soit l'ensemble des 2 premiers M n 4 nombres premiers. Le plus grand nombre premier est de taille au plus O ( M n 4 log M n ) . Choisissez un nombre premier p P aléatoire . Avec une probabilité élevée, p ne divisera aucun des éléments non nuls a b - c , nous pouvons donc représenter chacun a S par son résidu, mod p , et si 3 MUL en trouve a b = c dans SP2Mn4O(Mn4logMn)pPpabcaSp3ab=c , Avec une probabilité élevée, il sera correct pour l'instance 3 SUM d'origine. Nous avons réduit la plage des nombres à { 0 , , O ( M n 4 log M n ) }.S30,,O(Mn4logMn)

(Il s'agit d'une réduction de taille standard. Vous pourriez être en mesure de faire mieux en considérant le fait que les sont toujours des différences de deux puissances de 2. )abc2

virgi
la source
1
N'avez-vous pas réduit à 3MUL mod un premier plutôt que 3MUL? Il se peut que mais a b c . ab=c(mod()p)abc
Warren Schudy
1
Oui, tel quel, il s'agit d'une réduction à 3MUL mod p. Bon point.
virgi
Il s'agit d'une approche très intéressante. Cependant, nous sommes particulièrement intéressés par une réduction déterministe de 3-SUM à 3-MUL. Serait-il possible de dérandomiser la technique de réduction de taille?
Markus Jalsenius
3

Avez-vous essayé la réduction M = max S - min S ? Les résultats sont des nombres réels, vous devez donc arrondir à un certain nombre de chiffres. Pour vous assurer que les chiffres s'ajoutent correctement malgré l'arrondissement, vous devrez peut-être ajouter un peu de bruit aléatoire.S={2x/M|xS}M=maxSminS

Warren Schudy
la source
Oups, le bruit aléatoire ne semble pas suffisant pour corriger l'erreur d'arrondi. Cependant, ces idées semblent prometteuses pour réduire l'autre façon de montrer que 3-MULT n'est pas plus difficile que 3-SUM, car par exemple . (x+1)+y=x+y+1
Warren Schudy
1
L'équation ne semble pas correcte (essayez x et y = 2.1). Pourriez-vous clarifier ce que vous vouliez dire?
Raphael