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
SN - 0737-8017
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
T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979
Y2 - 30 April 1979 through 2 May 1979
ER -