Multiplikatywna wersja 3-SUM

22

Co wiadomo na temat złożoności czasowej następującego problemu, który nazywamy 3-MUL?

Biorąc pod uwagę zestaw z liczb całkowitych, czy są elementami taki sposób, że ? $S$ $n$ $a,b,c\in S$ $ab=c$

Ten problem jest podobny do problemu 3-SUM, który pyta, czy istnieją trzy elementy tak, że (lub równoważnie ). Przypuszcza się, że 3-SUM wymaga czasu z grubsza kwadratowego w . Czy istnieje podobna hipoteza dla 3-MUL? W szczególności czy wiadomo, że 3-MUL jest 3-SUMOWY twardy? $a,b,c\in S$ $a+b+c=0$ $a+b=c$ $n$

Uwaga: złożoność czasowa powinna mieć zastosowanie w „rozsądnym” modelu obliczeniowym. Na przykład możemy zmniejszyć z 3-SUM na zestawie do 3-MUL na zestawie , gdzie . Wtedy rozwiązanie 3-MUL, , istnieje wtedy i tylko wtedy, gdy . Jednak to wykładnicze powiększenie liczb skaluje się bardzo źle w przypadku różnych modeli, takich jak na przykład model pamięci RAM. $S$ $S'$ $S'=\{2^x\mid x\in S\}$ $2^a\cdot 2^b=2^c$ $a+b=c$

cc.complexity-theory ds.algorithms time-complexity

— Markus Jalsenius
źródło

Twoja redukcja pokazuje, że 3-MULT jest 3-SUMOWY twardy, jeśli liczby wejściowe można wyrazić za pomocą wykładniczej (aka naukowej) notacji.

— Warren Schudy,

4

Każdy algorytm dla 3-SUM, który opiera się wyłącznie na fakcie, że dodawanie jest grupą, może zostać przetłumaczony na algorytm dla 3-MULT i odwrotnie. Każdy algorytm oddzielający te dwa elementy musiałby zatem zrobić coś niezwykłego z liczbami.

— Warren Schudy,

1

aby być okropnie pedantycznym, potrzebujemy tylko półgrupy.

— Suresh Venkat,

11

Twoja redukcja z $3$ SUM do $3$ MUL działa z niewielką standardową modyfikacją. Załóżmy, że oryginalne liczby całkowite były w { $1,\ldots,M$ }. Po transformacji $x\rightarrow 2^x$ nowe liczby całkowite są w { $2,\ldots,2^M$ }. Zmniejszymy zasięg.

Rozważ dowolną potrójną liczbę całkowitą w nowym zestawie . Liczba pierwszych dzielników dowolnego niezerowego jest . Liczba takich potrójnych wynosi . Stąd liczba liczb pierwszych które dzielą co najmniej jedną z niezerowych liczb wynosi co najwyżej . $a,b,c$ $S'$ $ab-c$ $<2M$ $n^3$ $q$ $ab-c$ $2Mn^3$

Niech oznacza zbiór pierwszych pierwszymi. Największy takie pierwsza ma wielkość co najwyżej . Wybrać losowo prime . Z dużym prawdopodobieństwem nie podzieli żadnego z niezerowych , więc możemy przedstawić każdy przez jego resztę, mod , a jeśli MUL znajdzie jakieś w $P$ $2M\cdot n^4$ $O(Mn^4\log Mn)$ $p\in P$ $p$ $ab-c$ $a\in S'$ $p$ $3$ $ab=c$ Z dużym prawdopodobieństwem będzie poprawne dla oryginalnejinstancji SUM. Zmniejszyliśmy zakres liczb do { }. $S'$ $3$ $0,\ldots, O(Mn^4\log Mn)$

(Jest to standardowa redukcja rozmiaru. Możesz być w stanie zrobić to lepiej, biorąc pod uwagę fakt, że są zawsze różnicami dwóch potęg ). $ab-c$ $2$

— dziewice
źródło

1

Czy nie zredukowałeś do 3MUL mod prime zamiast 3MUL? Może być tak, że

ale

.

a b = c (\mod () p)

$ab=c \pmod(p)$

a b \neq c

$ab \ne c$

— Warren Schudy,

1

Tak, jak to jest, jest to redukcja do 3MUL mod p. Słuszna uwaga.

— virgi

To bardzo interesujące podejście. Jesteśmy jednak szczególnie zainteresowani deterministyczną redukcją z 3-SUMU do 3-MUL. Czy byłoby możliwe odstąpienie od techniki zmniejszania rozmiaru?

— Markus Jalsenius

3

Czy próbowałeś redukcji gdzie ? Wyniki są liczbami rzeczywistymi, więc musisz zaokrąglić do pewnej liczby cyfr. Aby zapewnić prawidłowe dodawanie liczb pomimo zaokrąglenia, może być konieczne dodanie odrobiny losowego szumu. $S'=\{2^{x/M}|x\in S\}$ $M=\max S− \min S$

— Warren Schudy
źródło

Ups, losowy hałas nie wydaje się wystarczający, aby naprawić błąd zaokrąglania. Jednak te pomysły wydają się obiecujące, że ograniczenie innego sposobu pokazania 3-MULT nie jest trudniejsze niż 3-SUM, ponieważ np. .

(⌈ x ⌉ + 1) + ⌈ y ⌉ = ⌈ x + y ⌉ + 1

$(\lceil x \rceil + 1) + \lceil y \rceil = \lceil x + y \rceil + 1$

— Warren Schudy,

1

Równanie nie wydaje się poprawne (spróbuj xiy = 2,1). Czy możesz wyjaśnić, co miałeś na myśli?

— Raphael