Juego de guijarros paralelos en línea

En el juego de guijarros en una línea hay N + 1 nodos etiquetados de 0 a N. El juego comienza con un guijarro en el nodo 0. Si hay un guijarro en el nodo i, puede agregar o quitar un guijarro del nodo i + 1. El objetivo es colocar una piedra en el nodo N, sin colocar muchas piedras en el tablero al mismo tiempo y sin dar demasiados pasos.

La solución ingenua es colocar una piedra en 1, luego en 2, luego en 3, y así sucesivamente. Esto es óptimo en términos de la cantidad de pasos. No es óptimo en la cantidad máxima de guijarros en el tablero al mismo tiempo: durante el último paso hay N guijarros en el tablero (sin contar el uno en 0).

En este documento se encuentra una estrategia que coloca menos guijarros en el tablero al mismo tiempo . Alcanzan el nodo N sin exceder los guijarros $\Theta(\lg N)$ a la vez, pero a costa de aumentar el número de pasos a $\Theta(n^{\lg_2 3})$ . Cambian si hay un guijarro en la posición sin dejar ningún otro guijarro alternando recursivamente , usándolo como un punto de partida para alternar con otro paso recursivo, luego alternando con un tercer paso recursivo de medio tamaño para Limpialo.$N$$N/2$$N$$N/2$

Estoy interesado en la compensación entre el número máximo de guijarros y el número de pasos, bajo el supuesto de que las adiciones y eliminaciones de guijarros se pueden hacer en paralelo. Por "paralelo" quiero decir que cada paso puede agregar o eliminar tantas piedras como se desee, siempre que se permita cada adición / eliminación individual y no interactúe con los otros movimientos que se están realizando. Específicamente, si es el conjunto de nodos de los que queremos agregar o quitar guijarros, y es el conjunto de nodos que tenía un guijarro al comienzo del paso, entonces podemos hacer todas esas adiciones y eliminaciones en un solo paso como siempre que .$A$$P$$\{a-1 | a \in A \} \subseteq P - A$

Por ejemplo, considere la estrategia que coloca un guijarro en en el paso , pero marca los guijarros que son múltiplos de como "puntos de verificación" y elimina el guijarro de índice más alto detrás de un punto de verificación de guijarros siempre que sea posible. Esta estrategia todavía alcanza el nodo N después de pasos, como la estrategia ingenua, pero reduce el número máximo de guijarros de a .$i$$i$$\sqrt{N}$$N$$N$$2 \sqrt{N}$

¿Existen estrategias de paralelismo de líneas paralelas que terminan en pasos con una complejidad de guijarros máximos asintóticos aún más baja? ¿Qué pasa si estamos dispuestos a permitir pasos ? ¿Cuáles son los puntos "interesantes", donde la compensación entre max-pebble y time es particularmente buena?O ( N lg N $N$$O(N \lg N)$

EDICIONES : Se agregaron Lemmas 2 y 3.

Aquí hay una respuesta parcial: puede alcanzar la posición $N$

• en mueve usando el espacio N O ( ϵ ( N ) ) , donde ϵ ( N ) = 1 / $N$$N^{O(\epsilon(N))}$ . (Lema 1)$\epsilon(N) = 1/\sqrt{\log N}$
• en mueve usando el espacio O ( log N ) (para cualquier constante δ > 0 ) (Lema 2).$N^{1+\delta}$$O(\log N)$$\delta>0$

Además, esbozamos un límite inferior (Lema 3): para una cierta clase de las llamadas soluciones de buen comportamiento , el Lema 1 es ajustado (hasta factores constantes en el exponente), y ninguna solución que use el espacio poli-log puede alcanzar posición en el tiempo O ( $N$ .$O(N\,\text{polylog}\, N)$

Lema 1. Para todo , es posible alcanzar la posición n en n movimientos usando el espacio exp ( O ( $n$$n$$n$

Prueba. El esquema es recursivo, como se muestra en la figura a continuación. Usamos la siguiente notación:

• es el número de niveles en la recursividad$k$
• es la solución formada (con k niveles de recursión).$P(k)$$k$
• es la posición máxima alcanzada por P ( k ) (en el momento N ( k ) ).$N(k)$$P(k)$$N(k)$
• es el espacio utilizado por P ( k ) .$S(k)$$P(k)$
• es el número decapasutilizadas por P ( k ) , como se ilustra a continuación:$L(k)$$P(k)$

En la imagen, el tiempo pasa de arriba a abajo. La solución no se detiene en el momento N ( k ) , sino que (para usar en la recursión) continúa hasta el tiempo $P(k)$$N(k)$ , invirtiendo exactamente sus movimientos, para volver a una sola piedra en el momento$2\,N(k)$ .$2\,N(k)$

Las líneas verticales continuas dividen las capas de P ( k ) . En la imagen, L ( k ) es cinco, entonces P ( k ) consta de 5 capas. Cada una de las capas L ( k ) de P ( k ) (excepto la más a la derecha) tiene dos subproblemas, uno en la parte superior de la capa y otro en la parte inferior, conectados por una línea vertical continua (que representa un guijarro que existe para esa duración). En la imagen, hay cinco capas, por lo que hay nueve subproblemas. En general, P $L(k)$$P(k)$$L(k)$$P(k)$$L(k)$$P(k)$ se compone de$P(k)$ subproblemas. Cada subproblema de P ( k ) tiene la solución P ( k - 1 ) .$2\,L(k)-1$$P(k)$$P(k-1)$

La observación crucial para delimitar el espacio es que, en cualquier momento, solo dos capas tienen subproblemas "activos". El resto aporta solo una piedra cada uno, así tenemos

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

Ahora, elegimos para determinar completamente P ( k ) . No estoy seguro de si esta opción es óptima, pero parece cercana: tome L ( k ) = 2 k . Entonces las recurrencias anteriores dan$L(k)$$P(k)$$L(k) = 2^k$

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

Entonces, resolviendo para , tenemos k ≈ $n=N(k)$ yS(k)≈$k \approx \sqrt {2 \log n}$. $S(k) \approx \sqrt {2 \log n}\, 2^{\sqrt {2 \log n}} = \exp(O(\sqrt{\log n}))$

Esto se ocupa de todas las posiciones en el conjunto { N ( k ) : k ∈ { 1 , 2 , ... } } . Para n arbitraria , recorte el fondo de la solución P ( k ) para la k más pequeña con N ( k ) ≥ n . El límite deseado se cumple porque 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)$

Lema 2. Para cualquier , para todo n , es posible alcanzar la posición n en n 1 + movimientos δ utilizando el espacio O ( δ 2 1 / δ log n ) $\delta>0$$n$$n$$n^{1+\delta}$$O(\delta 2^{1/\delta}\log n).$

Prueba. Modifique la construcción a partir de la prueba del Lema 1 para retrasar el inicio de cada subproblema hasta que el subproblema anterior haya terminado, como se muestra a continuación:

Deje que denote el tiempo para que termine la solución modificada P ( k ) . Ahora, en cada paso de tiempo, solo una capa tiene un subproblema que contribuye con más de una piedra, por lo que$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)$.

Choosing $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