Параллельная игра в гальку на линии

В игре с камушками на линии есть N + 1 узлы, обозначенные от 0 до N. Игра начинается с камешка на узле 0. Если на узле i есть камушек, вы можете добавить или удалить камешек из узла i + 1. Цель состоит в том, чтобы поместить гальку в узел N, не помещая одновременно много гальки на доску и не делая слишком много шагов.

Наивное решение состоит в том, чтобы поместить гальку в 1, затем в 2, затем в 3 и так далее. Это оптимально с точки зрения количества шагов. Это не оптимально для максимального количества камней на доске одновременно: на последнем шаге на доске есть N камней (не считая одного на 0).

В этой статье рассматривается стратегия, при которой на доске одновременно остается меньше камешков . Они достигают узла N, не превышая $\Theta(\lg N)$ камешков за раз, но за счет увеличения количества шагов до $\Theta(n^{\lg_2 3})$ . Они переключают, есть ли камешек в позиции $N$ не оставляя других камушков, рекурсивно переключая $N/2$ , используя это в качестве отправной точки для переключения $N$ с другим рекурсивным шагом, затем переключая $N/2$ с третьим рекурсивным шагом половинного размера в очисти это.

Меня интересует компромисс между максимальным количеством камешков и количеством шагов, при условии, что добавление и удаление камешков можно выполнять параллельно. Под «параллелью» я подразумеваю, что каждый шаг может добавлять или удалять столько камешков, сколько необходимо, при условии, что каждое отдельное добавление / удаление разрешено и не взаимодействует с другими выполняемыми движениями. В частности, если $A$ - это набор узлов, к которым мы хотим добавить или удалить камешки, а $P$ - это набор узлов, у которых был камешек в начале шага, тогда мы можем сделать все эти добавления и удаления за один шаг, как пока $\{a-1 | a \in A \} \subseteq P - A$ .

Например, рассмотрим стратегию, которая помещает камешек в на шаге i , но помечает камешки, кратные $i$$i$ как «контрольные точки» и удаляет гальку с самым высоким индексом позади контрольной точки, когда это возможно. Эта стратегия все еще достигает узла N послеNшагов, как и наивная стратегия, но уменьшает максимальное количество камешков сNдо2$\sqrt{N}$$N$$N$ .$2 \sqrt{N}$

Существуют ли стратегии параллельного выравнивания линий, которые заканчиваются за шагов с еще более низкой асимптотической сложностью max-pebble? Что, если мы хотим разрешить O ( N lg N ) шагов? Каковы «интересные» моменты, когда компромисс между max-pebble и временем особенно хорош?$N$$O(N \lg N)$

РЕДАКТИРОВАТЬ : Добавлены леммы 2 и 3.

Вот частичный ответ: Вы можете достичь позиции $N$

• в движется, используя пространство N O ( ϵ ( N ) ) , где ϵ ( N ) = 1 / $N$$N^{O(\epsilon(N))}$ . (Лемма 1)$\epsilon(N) = 1/\sqrt{\log N}$
• в движется с использованием пространства O ( log N ) (для любой постоянной δ > $N^{1+\delta}$$O(\log N)$$\delta>0$ ) (лемма 2).

Кроме того, мы рисуем нижнюю границу (лемма 3): для определенного класса так называемых решений с хорошим поведением лемма 1 является жесткой (с точностью до постоянных множителей в показателе степени), и никакое такое решение, использующее пространство с полулогами, не может достичь положение во времени$N$$O(N\,\text{polylog}\, N)$ .

Лемма 1. Для всех можно достичь положения n за n ходов, используя пробел exp ( O $n$$n$$n$

Доказательство. Схема рекурсивная, как показано на рисунке ниже. Мы используем следующие обозначения:

• - количество уровней в рекурсии$k$
• - сформированное решение (с k уровнями рекурсии).$P(k)$$k$
• - максимальная позиция, достигнутая P ( k ) (в момент времени N ( k ) ).$N(k)$$P(k)$$N(k)$
• - пространство, используемое P ( k ) .$S(k)$$P(k)$
• - количествослоев,используемых P ( k ) , как показано ниже:$L(k)$$P(k)$

На картинке время течет сверху вниз. Решение не останавливается в момент N ( k $P(k)$$N(k)$ , вместо этого (для использования в рекурсии) оно продолжается до времени $2\,N(k)$ , точно меняющий ходы, чтобы вернуться к одной гальке в момент времени $2\,N(k)$ .

Сплошные вертикальные линии разделяют слои группы P ( k ) . На рисунке L ( k ) равно пяти, поэтому P ( k ) состоит из 5 слоев. Каждый из L ( k ) слоев P ( k ) (кроме самого правого) имеет две подзадачи, одну в верхней части слоя и одну в нижней части, соединенные сплошной вертикальной линией (представляющей гальку, которая существует для эта продолжительность). На рисунке пять слоев, поэтому есть девять подзадач. Как правило,$L(k)$$P(k)$$L(k)$$P(k)$$L(k)$$P(k)$ состоит из$P(k)$ подзадача. Каждая подзадача в P ( k ) имеет решение P ( k - 1 ) .$2\,L(k)-1$$P(k)$$P(k-1)$

Критическое наблюдение для ограничения пространства состоит в том, что в любое время только два слоя имеют «активные» подзадачи. Остальные вносят только одну гальку, таким образом, мы имеем

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

Теперь мы выбираем чтобы полностью определить P ( k ) . Я не уверен, является ли этот выбор оптимальным, но он кажется близким: возьмем L ( k ) = 2 k . Тогда приведенные выше рецидивы дают$L(k)$$P(k)$$L(k) = 2^k$

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

Итак, решая для , имеем k ≈ $n=N(k)$ иS(k)≈$k \approx \sqrt {2 \log n}$. $S(k) \approx \sqrt {2 \log n}\, 2^{\sqrt {2 \log n}} = \exp(O(\sqrt{\log n}))$

Это учитывает все позиции в множестве { N ( k ) : k ∈ { 1 , 2 , … } } . Для произвольного n обрежьте дно решения P ( k ) для наименьшего k с N ( k ) ≥ n . Требуемая оценка выполняется, потому что 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. For any $\delta>0$, for all $n$, it is possible to reach position $n$ in $n^{1+\delta}$ moves using space $O(\delta 2^{1/\delta}\log n).$

Proof. Modify the construction from the proof of Lemma 1 to delay starting each subproblem until the previous subproblem has finished, as shown below:

Let $T(k)$ denote the time for the modified solution $P(k)$ to finish. Now at each time step, only one layer has a subproblem that contributes more than one pebble, so

• $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)$.

$L(k) = 2^{1/\delta}$, we get

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

Solving for $S = S(k)$ and $T=T(k)$ in terms of $n=N(k)$, we have $k=\delta \log n$, and

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

This takes care of all positions $n$ in the set $\{N(k) : k\in\{1,2,\ldots\}\}$. For arbitrary $n$, trim the bottom of the solution $P(k)$ for the smallest $k$ with $N(k)\ge n$. The desired bound holds because $S(k) / S(k-1) = O(1)$. QED

The solutions in the proofs of Lemmas 1 and 2 are well-behaved, in that, for sufficiently large $n$, for each solution $P(n)$ that reaches position $n$ there is a position $k\le n/2$ such that only one pebble is ever placed at position $k$, and the solution decomposes into a (well-behaved) solution $P(N-k)$ for positions $k+1,k+2,\ldots,n$ and two (well-behaved) solutions $P(k)$, each for positions $1,2,\ldots,k$, connected by the pebble at position $k$. With an appropriate definition of well-behaved, let $V(n)$ denote the minimum pebble volume (the sum over time of the number of pebbles at each time) for any well-behaved solution. The definition implies that for sufficiently large $n$, for $\delta=1>0$,

I conjecture that for every sufficiently large $n$ there is a well-behaved solution that minimizes pebble volume. Maybe somebody can prove it? (Or just that some near-optimal solution satisfies the recurrence...)

Recall that $\epsilon(n) = 1/\sqrt{\log n}$.

Lemma 3. For any constant $\delta>0$, the above recurrence implies $V(n) \ge n^{1+\Omega(\epsilon(n))}$.

Before we sketch the proof of the lemma, note that it implies that any well-behaved solution that reaches position $n$ in $t$ steps has to take space at least $n^{1+\Omega(\epsilon(n))}/t$ at some step. This yields corollaries such as:

• Lemma 1 is tight up to constant factors in the exponent (for well-behaved solutions).
• 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