Menemukan saksi dalam jumlah bilangan bulat minkowski

Biarkan dan menjadi himpunan bagian dari . Kami tertarik untuk menemukan jumlah Minkowski .$A$$B$$\{0,\ldots,n\}$$A+B=\{a+b~|~a\in A,b\in B\}$

$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ adalah fungsi karakteristik $X$ jika

Biarkan $f$ menjadi konvolusi diskrit dari $\chi_A$ dan $\chi_B$ , lalu $x\in A+B$ jika dan hanya jika $f(x)> 0$ . Karenanya $A+B$ dapat dihitung dalam waktu $O(n\log n)$ dengan konvolusi diskrit melalui FFT.

Terkadang penting untuk mengetahui pasangan aktual $a\in A$ dan $b\in B$ yang berjumlah $x$ . $a\in A$ disebut saksi dari $x$ , jika terdapat $b\in B$ sehingga $a+b=x$ . Fungsi $w:A+B\to A$ disebut fungsi saksi jika $w(x)$ adalah saksi $x$ .

Apakah mungkin untuk menghitung fungsi saksi dalam waktu $O(n\log n)$ ?

Di sini saya menjelaskan bagaimana cara mendapatkan $O(n *\mathrm{polylog} n)$ secara acak waktu berjalan. Kita membutuhkan urutan pengamatan:

1. Seorang saksi dari nilai $v$ adalah sepasang angka $(a,b) \in A \times B$ sehingga $a+b=v$ . Misalkan $P_A(x) = \sum_{i \in A} x^i$ dan $P_B(x)$ didefinisikan analog. Amati bahwa koefisien $x^v$ dalam $P_A(x) * P_B(x)$ adalah jumlah saksi yang ada untuk nilai$v$ .

2. Asumsikan $v$ memiliki saksi tunggal $(a,b) \in A \times B$ , dan pertimbangkan polinomial $Q_A(x) = \sum_{i \in A} i*x^i$ . Jelas, koefisien $x^v$ di $Q_A(x)*P_B(x)$ adalah $a$ , dan dengan demikian sekarang kita tahu pasangan $(a,v-a)$ dan kita selesai.

3. Jadi, kita selesai dengan kasus bahwa ada satu saksi. Jadi mempertimbangkan kasus yang memiliki k saksi ( a 1 , b 1 ) , ... , ( a k , b k ) . Biarkan saya ( k ) = ⌈ lg $v$$k$$(a_1, b_1),\ldots, (a_k,b_k)$. Perhatikan bahwa2i(k)-1≤$i(k) = \lceil{\lg \sqrt{k}}\rceil$ . Selanjutnya, misalkanRj=(Aj,Bj), untukj=1,...,m, untukm=O(logn)menjadi sampel acak, sehingga setiap elemenAdipilih menjadi Aidengan probabilitasp=1/2 i ( k ) . Probabilitas bahwa$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$memiliki saksi tunggal dalam adalah α = ($R_j$, karena saksi adalah pasangan angka yang terpisah (karena jumlah setiap pasangan adalahv). Sangat mudah untuk memverifikasi bahwaαadalah konstanta dalam(0,1)independen dari nilaik. Dengan demikian, itu harus, dengan probabilitas tinggi, yangvmemiliki saksi tunggal dalam salah satu sampelR1,...,Rm. Dengan demikian, dengan menghitung dua polinomial yang terkait dengan sampel tersebut, seperti dijelaskan di atas, pada$\alpha = \binom{k}{1}p^2 (1-p^2)^{k-1}$$v$$\alpha$$(0,1)$$k$$v$$R_1, \ldots, R_{m}$ waktu (per sampel), menggunakan FFT, kita dapat memutuskan ini dalam waktu yang konstan.$O(n \log n)$

4. Kami hampir selesai. Hitung sampel acak di atas untuk resolusi . Untuk setiap resolusi seperti itu hitung sampel acak dan polinomial terkait. Juga, menghitung polinomial terkait untuk A dan B . Preprocessing ini secara naif membutuhkan O ( n log 3 n ) , tetapi saya menduga bahwa menjadi sedikit lebih hati-hati faktor log n harus dilepas.$i=1,\ldots, \lceil\lg n\rceil$$A$$B$$O(n \log^3 n)$$\log n$

5. Algoritma: Untuk setiap nilai , hitung berapa banyak saksi, katakan k, ia memiliki waktu yang konstan, dengan berkonsultasi dengan polinomial Q A ( x ) ∗ P B ( x ) . Selanjutnya, pergi ke struktur data yang relevan untuk i ( k ) . Kemudian, ia menemukan sampel acak yang memilikinya sebagai saksi tunggal, dan itu mengekstrak pasangan yang adalah saksi ini dalam waktu yang konstan.$v$$Q_A(x)*P_B(x)$$i(k)$

6. Anehnya, waktu preprocessing adalah , tetapi waktu yang diharapkan untuk menemukan saksi sendiri hanya membutuhkan O ( n ) waktu, karena seseorang dapat menghentikan pencarian segera setelah seseorang menemukan saksi. Ini menunjukkan bahwa algoritma ini harus ditingkatkan. Secara khusus, untuk i ( k ) « lg n , polinomial yang dihasilkan sangat jarang, dan salah satu harus dapat melakukan jauh lebih cepat FFT.$O(n \log^3 n)$$O(n)$$i(k) \ll \lg n$

Ok, saya sudah menahan sejak Sariel benar-benar harus mendapatkan pujian untuk jawaban, tapi saya bosan menunggu, jadi di sini adalah saya potong di algoritma acak hampir linier.

• Dengan memilih sampel poin saya , i = 0 , 1 , ... , Anda bisa mendapatkan jumlah logaritmik subproblem sehingga setiap penjumlahan dari masalah asli memiliki probabilitas konstan untuk diwakili secara unik di salah satu subproblem ( yang mana pengambilan sampel mengurangi jumlah representasi yang diharapkan mendekati 1).$n(1-\epsilon)^i$$i=0,1,\dots$
• Dengan mengulangi proses pengambilan sampel sejumlah logaritmik, Anda bisa mendapatkan semua jumlah untuk memiliki representasi unik dengan probabilitas tinggi.
• Jika Anda memiliki partisi dan B menjadi dua himpunan bagian, maka dengan mengalikan angka dengan empat, menambahkan 2 ke angka-angka di salah satu himpunan bagian dalam A , dan menambahkan 1 ke angka-angka di salah satu himpunan bagian dalam B , Anda dapat bacalah dari nilai mod-4 dari jumlah yang dapat dicapai yang mana dari dua himpunan bagian dari mana mereka berasal.$A$$B$$A$$B$
• Dengan mengulangi proses partisi beberapa kali logaritmik, menggunakan setiap posisi bit dari representasi biner dari nilai-nilai atau indeks dalam subproblem untuk memilih partisi di setiap langkah, Anda dapat secara unik mengidentifikasi puncak dari setiap jumlah yang diwakili secara unik.

Ini meledakan waktu berjalan oleh tiga faktor logaritmik; mungkin itu bisa dikurangi.

Jawaban ini memberikan algoritma determinstic .$O(n~\mathrm{polylog} n)$

Tampaknya algoritma Sariel dan David dapat diderandomisasi melalui pendekatan yang mirip dengan makalah ini . [2] Saat menjalani proses ini, saya menemukan ada masalah yang lebih umum yang menyiratkan hasil ini.

Masalah rekonstruksi$k$

Ada yang tersembunyi set , kita memiliki dua nubuat S i z e dan S u m yang mengambil query set Q .$S_1,\ldots,S_n \subset \{1,\ldots,m\}$$Size$$Sum$$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)