The Pebbling Problem is Complete in Polynomial Space
John R. Gilbert, Thomas Lengauer, Robert Endre Tarjan · SIAM Journal on Computing · 1980
In this paper we study a pebbling problem that models the storage requirements of various kinds of computation. Sethi has shown this problem to be $NP$-hard and Lingas has shown a generalization to be P-space complete. We prove the original problem P-space complete by using a modification of Lingas’s proof. The pebbling problem is an example of a P-space complete problem not exhibiting any obvious quantifier alternation.