Multiplikative Version von 3-SUM

22

Was ist über die zeitliche Komplexität des folgenden Problems bekannt, das wir 3-MUL nennen?

Gibt es bei einer Menge von ganzen Zahlen Elemente so dass ?Sna,b,cSab=c

Dieses Problem ähnelt dem 3-SUM-Problem, bei dem gefragt wird, ob es drei Elemente so dass (oder äquivalent ). Es wird vermutet, dass 3-SUM ungefähr die quadratische Zeit in . Gibt es eine ähnliche Vermutung für 3-MUL? Insbesondere ist bekannt, dass 3-MUL 3-SUM hart ist?a,b,cSa+b+c=0a+b=cn

Beachten Sie, dass die zeitliche Komplexität in einem "vernünftigen" Berechnungsmodell gelten sollte. Zum Beispiel könnten wir von 3-SUM für eine Menge auf 3-MUL für die Menge reduzieren , wobei . Dann existiert eine Lösung für 3-MUL, , genau dann, wenn . Dieses exponentielle Aufblähen der Zahlen skaliert jedoch bei verschiedenen Modellen, wie beispielsweise dem RAM-Modell, sehr schlecht.SS ' = { 2 xx S } 2 a2 b = 2 c a + b = cSS={2xxS}2a2b=2ca+b=c

Markus Jalsenius
quelle
Ihre Reduktion zeigt, dass 3-MULT 3-SUM schwer ist, wenn die eingegebenen Zahlen in Exponentialschreibweise (auch bekannt als wissenschaftliche Schreibweise) ausgedrückt werden können.
Warren Schudy
4
Jeder Algorithmus für 3-SUM, der ausschließlich auf der Tatsache beruht, dass Addition eine Gruppe ist, kann in einen Algorithmus für 3-MULT übersetzt werden und umgekehrt. Jeder Algorithmus, der die beiden trennt, müsste daher mit den Zahlen etwas Ungewöhnliches anfangen.
Warren Schudy
1
Um schrecklich pedantisch zu sein, brauchen wir vielleicht nur eine Halbgruppe.
Suresh Venkat

Antworten:

11

Ihre Reduzierung von SUM auf MUL funktioniert mit einer geringfügigen Standardänderung. Angenommen, Ihre ursprünglichen Ganzzahlen befanden sich in { }. Nach der Transformation die neuen Ganzzahlen in { }. Wir werden die Reichweite reduzieren.3 1 , , M x 2 x 2 , , 2 M331,,Mx2x2,,2M

Betrachten Sie jedes Dreifache der ganzen Zahlen in der neuen Menge . Die Anzahl der Primteiler eines beliebigen von Null verschiedenen ist . Die Anzahl solcher Tripel ist . Daher beträgt die Anzahl der Primzahlen die mindestens eine der Zahlen ungleich Null teilen, höchstens .S ' a b - c < 2 M n 3 q a b - c 2 M n 3a,b,cSabc<2Mn3qabc2Mn3

Sei die Menge der ersten Primzahlen. Die größte solche Primzahl hat höchstens die Größe . Wähle eine zufällige Primzahl2 M n 4 O ( M n 4 log M n ) 0 , ... , O ( M n 4 log M n )P2Mn4O(Mn4logMn) . Mit hoher Wahrscheinlichkeitteilt p keines der a b - c ungleich Null, so dass wir jedes a S ' durch seinen Rest mod p darstellen können , und wenn 3 MULin S ' etwas a b = c finden , mit hoher Wahrscheinlichkeit wird für das Original 3 korrekt seinpPpabcaSp3ab=cS3SUM-Instanz. Wir haben den Bereich der Zahlen auf { } reduziert .0,,O(Mn4logMn)

(Dies ist eine Standardgrößenreduktion. Möglicherweise können Sie dies verbessern, wenn Sie die Tatsache berücksichtigen, dass die immer Differenzen zweier Potenzen von .)2abc2

virgi
quelle
1
Hast du nicht auf 3MUL Mod eine Primzahl anstatt auf 3MUL reduziert? Es kann sein, dass aber . a b cab=c(mod()p)abc
Warren Schudy
1
Ja, so wie es ist, ist dies eine Reduktion auf 3MUL mod p. Guter Punkt.
Virgi
Dies ist ein sehr interessanter Ansatz. Wir sind jedoch besonders an einer deterministischen Reduktion von 3-SUM auf 3-MUL interessiert. Wäre es vielleicht möglich, die Zerkleinerungstechnik zu derandomisieren?
Markus Jalsenius
3

Haben Sie die Reduktion mit versucht ? Die Ergebnisse sind reelle Zahlen, sodass Sie auf eine bestimmte Anzahl von Stellen runden müssen. Um sicherzustellen, dass die Zahlen trotz der Rundung korrekt addiert werden, müssen Sie möglicherweise etwas zufälliges Rauschen hinzufügen.M = max S - min SS={2x/M|xS}M=maxSminS

Warren Schudy
quelle
Hoppla, zufälliges Rauschen scheint nicht ausreichend zu sein, um den Rundungsfehler zu beheben. Diese Ideen scheinen jedoch vielversprechend zu sein, um die andere Art zu zeigen, dass 3-MULT nicht schwerer ist als 3-SUM, da zB . (x+1)+y=x+y+1
Warren Schudy
1
Die Gleichung scheint nicht korrekt zu sein (versuchen Sie x und y = 2.1). Könnten Sie klarstellen, was Sie meinten?
Raphael