The Pebbling Problem is Complete in Polynomial Space

Abstract

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.