Exact growth rate found for minimal space reversible pebbling
The Exact Growth Rate of Space-Optimal Reversible Pebbling on Chains
Computational Complexity
Summary
The paper finds the exact speed at which a specific computational process, called reversible pebbling on chains, grows over time when using the least possible memory space. The authors show this growth follows a precise number (about 1.33) that also applies uniformly for all chain lengths. This clarifies how efficiently a certain minimal memory computation can be performed and proves a formula that describes this growth rate.
What this means in practice
- •For complexity theorists: Define exact limits on time usage when computing with minimal memory on chain-like problems.
- •For algorithm designers: Guide design of reversible algorithms optimizing time when operating under strict space constraints on chain computations.
A theory result. No direct application yet.
Authors
Tetsuo Yokoyama
Abstract
We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\ldots$. 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.