TY - JOUR

T1 - The pebbling problem is complete in polynomial space

AU - Gilbert, John E.

AU - Lengauer, Thomas

AU - Tarjan, Robert Endre

N1 - Funding Information:
l/ Research partially supported by National Science Foundation Grant MCS-75-22870 A02 and Office of Naval Research Contract N00014-76-C-0688. Reproduction in whole or in part is permitted for any purpose of the United States government.
Funding Information:
22 Research partially supported by a Hertz Fellowship.
Publisher Copyright:
© 1979 Association for Computing Machinery. All rights reserved.

PY - 1979/4/30

Y1 - 1979/4/30

N2 - 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.

AB - 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.

KW - Computational complexity

KW - P-space completeness

KW - Pebbling

KW - Register allocation.

UR - http://www.scopus.com/inward/record.url?scp=84915686212&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84915686212&partnerID=8YFLogxK

U2 - 10.1145/800135.804418

DO - 10.1145/800135.804418

M3 - Conference article

AN - SCOPUS:84915686212

SP - 237

EP - 248

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0737-8017

T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979

Y2 - 30 April 1979 through 2 May 1979

ER -