The Pebbling Problem is Complete in Polynomial Space

We examine a pebbling problem which has been used to study the storage requirements of various models 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 employing a modification of Lingas's proof. The pebbling problem is one of the few examples of a P-space complete problem not exhibiting any obvious quantifier alternation.

Authors

• John R. Gilbert
• Thomas Lengauer
• Robert Endre Tarjan

Keywords

• Computational complexity
• P-space completeness
• Pebbling
• Register allocation