The pebbling problem is complete in polynomial space

John E. Gilbert, Thomas Lengauer, Robert Endre Tarjan

Research output: Contribution to journalConference article

10 Scopus citations

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 languageEnglish (US)
Pages (from-to)237-248
Number of pages12
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Apr 30 1979
Externally publishedYes
Event11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States
Duration: Apr 30 1979May 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