The Exact Growth Rate of Space-Optimal Reversible Pebbling on Chains

Abstract

We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\dots$. The growth rate of space-optimal reach exists as a limit and admits a variational formula. The same exponent governs complete computations at minimal space, uniformly in the chain length.