Game Paralel Kerikil di Garis

Dalam permainan kerikil pada garis ada N + 1 node berlabel 0 hingga N. Permainan dimulai dengan kerikil pada simpul 0. Jika ada kerikil pada simpul i, Anda dapat menambah atau menghapus kerikil dari simpul i +1. Tujuannya adalah untuk menempatkan kerikil pada simpul N, tanpa menempatkan banyak kerikil pada papan pada waktu yang bersamaan dan tanpa mengambil terlalu banyak langkah.

Solusi naif adalah menempatkan kerikil pada 1, lalu 2, kemudian 3, dan seterusnya. Ini optimal dalam hal jumlah langkah. Ini tidak optimal dalam jumlah maksimum kerikil di papan pada saat yang sama: selama langkah terakhir ada N kerikil di papan (tidak termasuk yang di 0).

Strategi yang menempatkan lebih sedikit kerikil di papan pada saat yang sama ada di makalah ini . Mereka mencapai simpul N tanpa melebihi $\Theta(\lg N)$ kerikil pada suatu waktu, tetapi dengan biaya meningkatkan jumlah langkah ke . Mereka beralih apakah ada kerikil pada posisi tanpa meninggalkan kerikil lain di sekitar dengan secara bergantian beralih , menggunakan itu sebagai titik awal untuk beralih dengan langkah rekursif lain, kemudian beralih dengan langkah rekursif setengah-setengah untuk jelas itu.$\Theta(n^{\lg_2 3})$$N$$N/2$$N$$N/2$

Saya tertarik pada tradeoff antara jumlah maksimum kerikil dan jumlah langkah, dengan asumsi bahwa penambahan dan pemindahan kerikil dapat dilakukan secara paralel. Maksud "paralel" yang saya maksud adalah bahwa setiap langkah dapat menambah atau menghapus sebanyak mungkin kerikil yang diinginkan, selama setiap penambahan / pemindahan individu diizinkan dan tidak berinteraksi dengan gerakan lain yang sedang dibuat. Secara khusus, jika adalah himpunan node yang ingin kita tambahkan atau hapus kerikil, dan adalah himpunan node yang memiliki kerikil pada awal langkah, maka kita dapat melakukan semua penambahan dan pemindahan tersebut dalam satu langkah sebagai selama .$A$$P$$\{a-1 | a \in A \} \subseteq P - A$

Misalnya, pertimbangkan strategi yang menempatkan kerikil pada pada langkah , tetapi tandai kerikil yang merupakan kelipatan dari sebagai "pos pemeriksaan" dan menghapus kerikil indeks tertinggi di belakang pos pemeriksaan kerikil bila memungkinkan. Strategi ini masih mencapai simpul N setelah langkah , seperti strategi naif, tetapi mengurangi jumlah maksimum kerikil dari menjadi .$i$$i$$\sqrt{N}$$N$$N$$2 \sqrt{N}$

Apakah ada strategi kerikil paralel-garis yang selesai dalam langkah-langkah dengan kompleksitas max-kerikil asimtotik yang lebih rendah? Bagaimana jika kami bersedia mengizinkan langkah ? Apa poin "menarik", di mana pengorbanan antara kerikil maksimal dan waktu sangat baik?$N$$O(N \lg N)$

EDIT : Menambahkan Lemmas 2 dan 3.

Ini jawaban parsial: Anda dapat mencapai posisi $N$

• di bergerak menggunakan spasi N O ( ϵ ( N ) ) , di mana ϵ ( N ) = 1 / $N$$N^{O(\epsilon(N))}$ . (Lemma 1)$\epsilon(N) = 1/\sqrt{\log N}$
• pada bergerak menggunakan spasi O ( log N ) (untuk konstanta δ > 0 ) (Lemma 2).$N^{1+\delta}$$O(\log N)$$\delta>0$

Juga, kami membuat sketsa batas bawah (Lemma 3): untuk kelas tertentu dari apa yang disebut solusi berperilaku baik , Lemma 1 ketat (hingga faktor konstan dalam eksponen), dan tidak ada solusi seperti itu menggunakan ruang poly-log dapat mencapai posisi dalam waktu O ( $N$ .$O(N\,\text{polylog}\, N)$

Lemma 1. Untuk semua , dimungkinkan untuk mencapai posisi n dalam n bergerak menggunakan exp ruang ( O ( $n$$n$$n$

Bukti. Skema ini bersifat rekursif, seperti yang ditunjukkan pada gambar di bawah ini. Kami menggunakan notasi berikut:

• adalah jumlah level dalam rekursi$k$
• adalah solusi yang terbentuk (dengantingkat rekursi k ).$P(k)$$k$
• adalah posisi maksimum yang dicapai oleh P ( k ) (pada saat N ( k ) ).$N(k)$$P(k)$$N(k)$
• adalah ruang yang digunakan oleh P ( k ) .$S(k)$$P(k)$
• adalah jumlahlapisan yangdigunakan oleh P ( k ) , seperti yang diilustrasikan di bawah ini:$L(k)$$P(k)$

Dalam gambar, waktu mulai dari atas ke bawah. Solusi tidak berhenti pada waktu N ( k ) , sebagai gantinya (untuk digunakan dalam rekursi) itu berlanjut sampai waktu $P(k)$$N(k)$ , tepatnya membalikkan gerakannya, sehingga dapat kembali ke kerikil tunggal pada waktu$2\,N(k)$ .$2\,N(k)$

Garis vertikal solid mempartisi lapisan dari P ( k ) . Dalam gambar, L ( k ) adalah lima, jadi P ( k ) terdiri dari 5 lapisan. Masing-masing dari L ( k ) lapisan P ( k ) (kecuali paling kanan) memiliki dua sub-masalah, satu di bagian atas lapisan dan satu di bagian bawah, terhubung oleh garis vertikal yang solid (mewakili kerikil yang ada untuk durasi itu). Dalam gambar, ada lima lapisan, jadi ada sembilan submasalah. Umumnya, P $L(k)$$P(k)$$L(k)$$P(k)$$L(k)$$P(k)$ terdiri dari$P(k)$ submasalah. Setiap sub masalah dari P ( k ) memiliki solusi P ( k - 1 ) .$2\,L(k)-1$$P(k)$$P(k-1)$

Pengamatan penting untuk membatasi ruang adalah bahwa, setiap saat, hanya dua lapisan yang memiliki subproblem "aktif". Sisanya berkontribusi masing-masing satu kerikil yang kita miliki

• , dan$S(k) \le L(k) + 2\,S(k-1)$
• $N(k) = L(k) \cdot N(k-1)$

Sekarang, kami memilih untuk sepenuhnya menentukan P ( k ) . Saya tidak yakin apakah pilihan ini optimal, tetapi tampaknya dekat: ambil L ( k ) = 2 k . Kemudian rekurensi di atas memberi$L(k)$$P(k)$$L(k) = 2^k$

• , dan$S(k) \le k\cdot 2^k$
• $N(k) = 2^{k(k+1)/2}$

Jadi, penyelesaian untuk , kita memiliki k ≈ $n=N(k)$ danS(k)≈$k \approx \sqrt {2 \log n}$. $S(k) \approx \sqrt {2 \log n}\, 2^{\sqrt {2 \log n}} = \exp(O(\sqrt{\log n}))$

Ini menangani semua posisi dalam set { N ( k ) : k ∈ { 1 , 2 , … } } . Untuk n sembarang , pangkas bagian bawah larutan P ( k ) untuk k terkecil dengan N ( k ) ≥ n . Batas yang diinginkan berlaku karena S ( k ) / S ( k - 1 ) = O $n$$\{N(k) : k\in\{1,2,\ldots\}\}$$n$$P(k)$$k$$N(k)\ge n$ . QED$S(k) / S(k-1) = O(1)$

Lemma 2. Untuk , untuk semua n , dimungkinkan untuk mencapai posisi n dalam n 1 + δ bergerak menggunakan spasi O ( δ 2 1 / δ log n ) $\delta>0$$n$$n$$n^{1+\delta}$$O(\delta 2^{1/\delta}\log n).$

Bukti. Ubah konstruksi dari bukti Lemma 1 untuk menunda memulai setiap subproblem hingga subproblem sebelumnya selesai, seperti yang ditunjukkan di bawah ini:

Biarkan menunjukkan waktu penyelesaian solusi P ( k ) yang selesai. Sekarang pada setiap langkah waktu, hanya satu lapisan yang memiliki subproblem yang menyumbang lebih dari satu kerikil, jadi$T(k)$$P(k)$

• ,$S(k) \le L(k) + S(k-1)$
• ,$N(k) = L(k) \cdot N(k-1)$
• .$T(k) = (2\,L(k)-1)\cdot T(k-1) \le 2\,L(k)\cdot T(k-1) \le 2^k N(k)$

Memilih , kita dapatkan$L(k) = 2^{1/\delta}$

• ,$S(k) \le k 2^{1/\delta}$
• ,$N(k) = 2^{k/\delta}$
• .$T(k) \le 2^k N(k)$

Memecahkan untuk dan T = T ( k ) dalam hal n = N ( k ) , kita memiliki k = δ log n , dan$S = S(k)$$T=T(k)$$n=N(k)$$k=\delta \log n$

• , dan$S \le \delta 2^{1/\delta} \log n$
• . $T \le n^{1+\delta}$

Ini menangani semua posisi dalam set { N ( k ) : k ∈ { 1 , 2 , … } } . Untuk n sembarang , pangkas bagian bawah larutan P ( k ) untuk k terkecil dengan N ( k ) ≥ n . Batas yang diinginkan berlaku karena S ( k ) / S ( k - 1 ) = O $n$$\{N(k) : k\in\{1,2,\ldots\}\}$$n$$P(k)$$k$$N(k)\ge n$ . QED$S(k) / S(k-1) = O(1)$

Solusi dalam bukti Lemmas 1 dan 2 berperilaku baik , dalam hal itu, untuk cukup besar , untuk setiap solusi P ( n ) yang mencapai posisi n ada posisi k ≤ n / 2 sehingga hanya satu kerikil yang pernah ada ditempatkan pada posisi k , dan solusi terurai menjadi solusi (berperilaku baik) P ( N - k ) untuk posisi k + 1 , k + 2 , … , n dan dua solusi (berperilaku baik)$n$$P(n)$$n$$k\le n/2$$k$$P(N-k)$$k+1,k+2,\ldots,n$ , masing-masing untuk posisi 1 , 2 , ... , k , dihubungkan oleh kerikil di posisi k . Dengan definisi yang tepat tentangperilaku baik, misalkan V ( n ) menunjukkanvolume kerikilminimum(jumlah dari waktu ke waktu jumlah kerikil pada setiap waktu) untuk solusi apa pun yang berperilaku baik. Definisi tersebut menyiratkan bahwa untuk n yang cukup besar, untuk δ = 1 > 0 , V ( n ) ≥ min k $P(k)$$1,2,\ldots,k$$k$$V(n)$$n$$\delta=1>0$

Saya menduga bahwa untuk setiap cukup besar ada solusi yang berperilaku baik yang meminimalkan volume kerikil. Mungkin seseorang bisa membuktikannya? (Atau hanya beberapa solusi yang hampir optimal memenuhi pengulangan ...)$n$

Ingat bahwa .$\epsilon(n) = 1/\sqrt{\log n}$

Lemma 3. Untuk konstanta , pengulangan di atas menyiratkan V ( n ) ≥ n 1 + Ω ( ϵ ( n ) ) .$\delta>0$$V(n) \ge n^{1+\Omega(\epsilon(n))}$

Sebelum kita membuat sketsa bukti lemma, perhatikan bahwa itu menyiratkan bahwa setiap solusi berperilaku baik yang mencapai posisi dalam t langkah harus mengambil ruang setidaknya n 1 + Ω ( ϵ ( n ) ) / t pada beberapa langkah. Ini menghasilkan akibat wajar seperti:$n$$t$$n^{1+\Omega(\epsilon(n))}/t$

• Lemma 1 ketat hingga faktor konstan dalam eksponen (untuk solusi yang berperilaku baik).
• No well-behaved solution can reach position $n$ in $n\,\text{polylog}\, n$ time steps using space $\text{polylog}\, n$. (Using here that $n^{\Omega(\epsilon(n))} = \exp(\Omega(\sqrt{\log n})) \not\subseteq \,\text{polylog}\, n$.)

Proof sketch. We show $2 V(n) \ge f(n)$ where $f(n) = n^{1+c\epsilon(n)}$ for some sufficiently small constant $c.$ We assume WLOG that $n$ is arbitrarily large, because by taking $c>0$ small enough, we can ensure $2 V(n) \ge f(n)$ for any finite set of $n$ (using here that $V(n)\ge n$, say).

The lemma will follow inductively from the recurrence as long as, for all sufficiently large $n$, we have $f(n) \le \min_{k<n} f(n-k) + \max(n, 2 f(k))$, that is, $f(n) - f(n-k) \le \max(n, (1+\delta) f(k))$ for $k<n.$

Since $f$ is convex, we have $f(n) - f(n-k) \le k f'(n)$. So it suffices if $k f'(n) \le \max(n, (1+\delta) f(k)).$

By a short calculation (using $f(n)/n = e^{c\sqrt{\log n}}$ and $f'(n)=(f(n)/n)(1+c/(2\sqrt{\log n})),$ and using a change of variables $x = \sqrt{\log k}$ and $y=\sqrt{\log n}$), this inequality is equivalent to the following: for all sufficiently large $y$ and $x\le y$, $e^{cy}(1+c/(2y)) \le \max(e^{y^2 - x^2}, (1+\delta) e^{cx})$. Since $1+z\le e^z$, and $e^z\le 1+2z$ for $z\le 1$, it suffices to show $e^{cy + c/(2y)} \le \max(e^{y^2 - x^2}, e^{2\delta+cx}),$ that is,

If $y \le x + 0.1\delta/c$, then $cy+c/(2y) \le cx + 0.2\delta$ (for large $y$) and we are done, so assume $y\ge x + 0.1\delta/c$. Then $y^2-x^2 \ge 0.1y\delta/c$ (for large $y$), so it suffices to show