### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 237-248 |

Number of pages | 12 |

Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - Apr 30 1979 |

Externally published | Yes |

Event | 11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States Duration: Apr 30 1979 → May 2 1979 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

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

## Fingerprint Dive into the research topics of 'The pebbling problem is complete in polynomial space'. Together they form a unique fingerprint.

## Cite this

Gilbert, J. E., Lengauer, T., & Tarjan, R. E. (1979). The pebbling problem is complete in polynomial space.

*Proceedings of the Annual ACM Symposium on Theory of Computing*, 237-248. https://doi.org/10.1145/800135.804418