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)|
|Number of pages||12|
|Journal||Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Apr 30 1979|
|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
- Computational complexity
- P-space completeness
- Register allocation.