平行したペブルゲーム

1行のペブルゲームには、0からNまでのN +
1個のノードがあります。ゲームが始まりますノード0に小石があります。ノードiに小石がある場合は、ノードi +
1に小石を追加または削除できます。目標は、同時に多くの小石をボード上に配置することなく、あまりに多くのステップを踏まずにノードNに小石を配置することです。

素朴な解決策は、1の上に小石を配置し、次に2に、次に3に小石を配置することです。これはステップ数の点で最適です。同時にボードの最大数の小石では最適ではありません。最後のステップではボードにN個の小石があります(0のものは数えません)。

同じ時間にボードに少数の小石を配置する戦略は、このペーパーにあります。一度に$ Theta( lg
N)$小石を超えずにノードNに到達しますが、ステップ数を$ Theta(n ^ { lg_2 3})$に増やす犠牲になります。
$ N/2 $を再帰的にトグルすることで、他の小石を残さずに位置$ N
$に小石があるかどうかをトグルします。これを出発点として別の再帰的ステップで$ N $を切り替えてから$ N/2
$それをクリアするための第3のハーフサイズの再帰的ステップ。

私は、小石の追加と削除を並行して行うことができるという前提のもと、小石の最大数と歩数のトレードオフに興味があります。
「平行」とは、個々の追加/削除が許可され、他の移動が行われていない限り、各ステップが必要に応じて多くの小石を追加または削除できることを意味します。具体的には、$
A $が小石を追加または削除したいノードの集合であり、$ P
$がステップの開始時に小石を持つノードの集合である場合、それらの追加と削除をすべて$ {a-1 | \ A }
subseteq P – A $のである。

たとえば、ステップ$ i $で小石を$ i $に配置し、$ sqrt {N}
$の倍数である小石を「チェックポイント」としてマークし、pebbleされたチェックポイントの背後にある最も高いインデックスの小石を削除する戦略を考えてみましょういつでも可能なとき。この戦略はまだナイーブな戦略のように$
N $ステップの後にノードNに到達しますが、$ N $から$ 2 sqrt {N} $までの小石の最大数を減らします。

$ N $ステップで終わるparrallel-line-pebbling戦略がありますか? $ O(N lg
N)$ステップを許可する場合はどうなりますか?マックス・ペブルと時間の間のトレードオフが特に良い「面白い」ポイントは何ですか?

ベストアンサー

EDITS: Added Lemmas 2 and 3.

ここに部分的な答えがあります:ポジション$ N $

  • in $N$ moves using space $N^{O(epsilon(N))}$, where
    $epsilon(N) = 1/sqrt{log N}$. (Lemma 1)
  • in $N^{1+delta}$ moves using space $O(log N)$ (for any
    constant $delta>0$) (Lemma 2).

また、我々は下限をスケッチする(補題3):いわゆるよく振舞う解の特定のクラスに対して、補題1は厳密(指数の定数まで)であり、そのような解はないポリログ空間を使用すると、時間$
O(N 、 text {ポリロッグ} 、​​N)$の位置$ N $に到達することができます。

Lemma 1. For all $n$, it is possible to
reach position $n$ in $n$ moves using space $$exp(O(sqrt{log
n}))~=~n^{O(1/sqrt{log n})}$$

Proof. The scheme is recursive, as shown in the figure
below. We use the following notation:

  • $ k $は再帰のレベル数です。
  • $ P(k)$は、(k $再帰のレベルで)形成された解です。
  • $ N(k)$は、$ P(k)$(時刻$ N(k)$)で到達する最大位置です。
  • $ S(k)$は$ P(k)$が使用するスペースです。
  • $ L(k)$は、$ P(k)$で使用されるレイヤーの数です。

                  solution structure for lemma 1

写真では、時間は上から下に向かって進みます。解$ P(k)$は時間$
N(k)$で停止せず、代わりに(再帰で使用するために)時間$ 2 、N(k)$まで継続し、時間$ 2
、N(k)$の単一小石に変換します。

実線の垂直線は、$ P(k)$の$ L(k)$層を分割する。画像では、$ L(k)$は5であるので、$
P(k)$は5つのレイヤーで構成されています。 $ P(k)$の$
L(k)$層のそれぞれ(右端を除く)には、層の上端と下端の2つの副問題があります。その期間に存在する小石)。画像には5つのレイヤーがあるため、9つのサブ問題があります。一般に、$
P(k)$は$ 2 、L(k)-1 $部分問題で構成されます。 $ P(k)$の各部分問題は解P(k-1)$を有する。

空間の境界を定める重要な観察は、いつでも2つの層だけが「能動的」副問題を有することである。残りはそれぞれ1つの小石にしか寄与しないので、

    S(k-1)$、および(k-1)$

今、$ P(k)$を完全に決定するために$
L(k)$を選択します。この選択肢が最適かどうかは分かりませんが、近いと思われます。$ L(k)= 2 ^ k
$を取る。その後、上記の再発は

  • $ S(k) le k cdot 2 ^ k $、
  • (k)= 2 ^ {k(k + 1)/ 2} $

したがって、$ n = N(k)$を解くと、 我々は$ k approx sqrt {2 log n} $ $ 2
$ { sqrt { sqrt {2 log n}} = exp(O( sqrt { log
n}))$である。

これは、 {N(k):k 1,2、 ldots } } $内のすべての位置$ n $を処理します。任意の$ n
$に対して、$ N(k) ge n $でもっとも小さい$ k $の解の$ P(k)$をトリムします。 $ S(k)/ S(k-1)=
O(1)$であるので、所望の境界が保持される。 QED


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:

                  solution structure for lemma 2

$ T(k)$は修正された解$
P(k)$が終了する時間を示すものとする。現在の各ステップでは、1つのレイヤーに1つ以上の小石が寄与する部分問題があるため

    (k)+ S(k-1)$、(k-1)$、L(k-1) le 2 ^ k(k-1)は、 N(k)$。

$ L(k)= 2 ^ {1/ delta} $を選択すると、

  • $ S(k) le k 2 ^ {1/ delta} $、
  • $ N(k)= 2 ^ {k/ delta} $、
  • $ T(k) le 2 ^ k N(k)$。

$ n = N(k)$の観点から$ S = S(k)$と$ T = T(k)$を解くと、$ k = delta log
n $となる。

  • $ S le delta 2 ^ {1/ delta} log n $、および
  • $ T le n ^ {1+ delta} $。

これは、 {N(k):k 1,2、 ldots } } $内のすべての位置$ n $を処理します。任意の$ n
$に対して、$ N(k) ge n $でもっとも小さい$ k $の解の$ P(k)$をトリムします。 $ 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
$kle 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$, $$V(n) ge
min_{k

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})) notsubseteq ,text{polylog},
    n$.)

Proof sketch. We show $2 V(n) ge f(n)$ where $f(n) =
n^{1+cepsilon(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

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^{csqrt{log n}}$ and
$f'(n)=(f(n)/n)(1+c/(2sqrt{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 $xle y$, $e^{cy}(1+c/(2y)) le max(e^{y^2 – x^2},
(1+delta) e^{cx})$. Since $1+zle e^z$, and $e^zle 1+2z$ for
$zle 1$, it suffices to show $e^{cy + c/(2y)} le max(e^{y^2 –
x^2}, e^{2delta+cx}),$ that is, $$cy + c/(2y) le max(y^2 – x^2,
2delta+cx).$$

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

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です