Znalezienie świadka w minkowskiej sumie liczb całkowitych

Niech i będą podzbiorami . Interesuje nas znalezienie sumy Minkowskiego .$A$$B$$\{0,\ldots,n\}$$A+B=\{a+b~|~a\in A,b\in B\}$

$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ jest charakterystyczną funkcją if$X$

Niech będzie dyskretne splot i , a , wtedy i tylko wtedy, . Zatem można obliczyć w czasie poprzez dyskretne splotowanie za pomocą FFT.$f$$\chi_A$$\chi_B$$x\in A+B$$f(x)> 0$$A+B$$O(n\log n)$

Czasami ważne jest znalezienie rzeczywistej pary i która sumuje się do x . A \ w A nazywany jest świadectwem z X , jeśli istnieją b \ B w taki sposób, że a + b = X . Funkcja w: A + B \ do A nazywa się funkcją świadka, jeśli w (x) jest świadkiem x .$a\in A$$b\in B$$x$$a\in A$$x$$b\in B$$a+b=x$$w:A+B\to A$$w(x)$$x$

Czy można obliczyć funkcję świadka w czasie $O(n\log n)$ ?

Wyjaśniam tutaj, jak uzyskać losowy czas działania $O(n *\mathrm{polylog} n)$ . Potrzebujemy sekwencji obserwacji:

1. Świadczyć o wartości $v$ jest para numerów $(a,b) \in A \times B$ , tak że + b = V . Niech P A ( x ) = ∑ i ∈ A x i i P B ( x ) zostaną zdefiniowane analogicznie. Zauważ, że współczynnik x v w P A ( x ) ∗ P B ( x$a+b=v$$P_A(x) = \sum_{i \in A} x^i$$P_B(x)$$x^v$) to liczba świadków o wartości v .$P_A(x) * P_B(x)$$v$

2. Załóżmy, v ma jeden świadka ( a , b ) ∈ A × B i rozważyć wielomian Q A ( x ) = Σ i ∈ i * x ı . Oczywiście współczynnik x v w Q A ( x ) ∗ P B ( x ) wynosi a , i jako taki, znamy teraz parę ( a , v - a $v$$(a,b) \in A \times B$$Q_A(x) = \sum_{i \in A} i*x^i$$x^v$$Q_A(x)*P_B(x)$$a$$(a,v-a)$ i skończymy.

3. Skończyliśmy już ze sprawą, że jest jeden świadek. Rozważmy więc przypadek, w którym v ma k świadków ( a 1 , b 1 ) , … , ( a k , b k ) . Niech i ( k ) = ⌈ lg $v$$k$$(a_1, b_1),\ldots, (a_k,b_k)$k ⌉. Zauważ, że2i(k)-1≤$i(k) = \lceil{\lg \sqrt{k}}\rceil$k ≤2 i ( k ) . Następnie pozwolićRj=(j,Bj)dlaj=1,...,m, dlam=O(logn)są losowymi próbki, tak, że każdy elementAjest Choosen do Aız prawdopodobieństwemp=1/2 I ( k ) . Prawdopodobieństwo, że$2^{i(k)-1} \leq \sqrt{k} \leq 2^{i(k)}$$R_j = (A_j, B_j)$$j=1,\ldots, m$$m=O(\log n)$$A$$A_i$$p = 1/2^{i(k)}$$v$zawiera jeden świadkiem w R j jest α = ($R_j$1 ) p2(1-p2)k-1, ponieważ świadkiem są rozłączne pary liczb (ponieważ suma każdej pary wynosiv). Łatwo jest sprawdzić, czyαjest stałą w(0,1)niezależną od wartościk. Jako taka, musi być z dużym prawdopodobieństwem, żeVjest pojedynczy świadkiem w jednej z próbekR1,...,Rm. Jako taki, obliczając dwa wielomiany związane z taką próbką, jak opisano powyżej, w$\alpha = \binom{k}{1}p^2 (1-p^2)^{k-1}$$v$$\alpha$$(0,1)$$k$$v$$R_1, \ldots, R_{m}$O ( n log n ) czas (na próbkę), używając FFT, możemy zdecydować o tym w stałym czasie.$O(n \log n)$

4. Prawie skończyliśmy. Oblicz powyższe losowe próbki dla rozdzielczości i = 1 , … , ⌈ lg n ⌉ . Dla każdej takiej rozdzielczości oblicz losowe próbki i powiązane wielomiany. Również wyliczy wielomianu dla A i B . To wstępne przetwarzanie naiwnie zajmuje O ( n log 3 n ) , ale podejrzewam, że przy nieco większej ostrożności współczynnik log n powinien być możliwy do usunięcia.$i=1,\ldots, \lceil\lg n\rceil$$A$$B$$O(n \log^3 n)$$\log n$

5. The algorithm: For every value $v$, compute how many witness, say k, it has in constant time, by consulting the polynomial $Q_A(x)*P_B(x)$. Next, go to the relevant data-structure for $i(k)$. Then, it finds the random sample that has it as a single witness, and it extract the pair that is this witness in constant time.

6. O dziwo, czas wstępnego przetwarzania wynosi O ( n log 3 n ) , ale oczekiwany czas znalezienia samego świadka zajmuje tylko O ( n ) , ponieważ można zatrzymać poszukiwania, gdy tylko znajdzie się świadka. Sugeruje to, że ten algorytm powinien być możliwy do ulepszenia. W szczególności, dla i ( k ) ≪ lg n , generowane wielomiany są bardzo rzadkie i powinno być możliwe wykonanie znacznie szybszej FFT.$O(n \log^3 n)$$O(n)$$i(k) \ll \lg n$

Ok, I've been holding off since really Sariel should get credit for an answer, but I'm tired of waiting, so here is my cut at a near-linear randomized algorithm.

• By choosing samples of $n(1-\epsilon)^i$ points, $i=0,1,\dots$, you can get a logarithmic number of subproblems such that each sum from the original problem has constant probability of being represented uniquely in one of the subproblems (the one where the sampling cuts down the expected number of representations to near 1).
• By repeating the sampling process a logarithmic number of times you can get all sums to have unique representations with high probability.
• If you have a partition of $A$ and $B$ into two subsets, then by multiplying the numbers by four, adding 2 to the numbers in one of the subsets in $A$, and adding 1 to the numbers in one of the subsets in $B$, you can read off from the mod-4 values of the achievable sums which of the two subsets their summands come from.
• By repeating the partition process a logarithmic number of times, using each bit position of the binary representations of the values or indices in the subproblems to select the partitions in each step, you can uniquely identify the summands of every uniquely-represented sum.

This blows up the running time by three logarithmic factors; probably that can be reduced.

This answer gives a determinstic $O(n~\mathrm{polylog} n)$ algorithm.

It appears that Sariel and David's algorithm can be derandomized through an approach similar to this paper. [2] While going through the process I found there is a more general problem that implies this result.

The $k$-reconstruction problem

There are hidden sets $S_1,\ldots,S_n \subset \{1,\ldots,m\}$, we have two oracles $Size$ and $Sum$ that take a query set $Q$.

1. $Size(Q)$ returns $(|S_1\cap Q|,|S_2\cap Q|,\ldots,|S_n\cap Q|)$, the size of each intersection.
2. $Sum(Q)$ returns $(\sum_{s\in S_1\cap Q} s,\sum_{s\in S_2\cap Q} s,\ldots,\sum_{s\in S_n\cap Q} s)$, the sum of elements in each intersection.

The $k$-reconstruction problem asks one to find $n$ subsets $S_1',\ldots,S_n'$ such that $S_i'\subset S_i$ and $|S_i'|=\min(k,|S_i|)$ for all $i$.

Let $f$ be the running time of calling the oracles, and assume $f=\Omega(m+n)$, then one can find the sets in deterministic $O(f k \log n~\mathrm{polylog}(m))$ time. [1]

Now we can reduce the finding witness problem to $1$-reconstruction problem. Here $S_1,\ldots,S_{2n}\subset \{1,\ldots,2n\}$ where $S_i = \{a|a+b = i, a\in A, b\in B\}$.

Define the polynomials $\chi_Q(x) = \sum_{i \in Q} x^i$, $I_Q(x) = \sum_{i \in Q} i x^i$

The coefficient for $x^i$ in $\chi_Q\chi_B(x)$ is $|S_i\cap Q|$ and in $I_Q\chi_B(x)$ is $\sum_{s\in S_i\cap Q} s$. Hence the oracles take $O(n\log n)$ time per call.

This gives us an $O(n~\mathrm{polylog}(n))$ time deterministic algorithm.

[1] Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur: Finding witnesses by peeling. ACM Transactions on Algorithms 7(2): 24 (2011)

[2] Noga Alon, Moni Naor: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16(4-5) (1996)