The pebbling problem is complete in polynomial space

John E. Gilbert; Thomas Lengauer; Robert Endre Tarjan

doi:10.1145/800135.804418

The pebbling problem is complete in polynomial space

John E. Gilbert, Thomas Lengauer, Robert Endre Tarjan

Research output: Contribution to journal › Conference article › peer-review

18 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 language	English (US)
Pages (from-to)	237-248
Number of pages	12
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800135.804418
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.

Access to Document

10.1145/800135.804418

Cite this

@article{246277ec533d4d9a83d206c61bcd7262,

title = "The pebbling problem is complete in polynomial space",

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.",

keywords = "Computational complexity, P-space completeness, Pebbling, Register allocation.",

author = "Gilbert, \{John E.\} and Thomas Lengauer and Tarjan, \{Robert Endre\}",

note = "Publisher Copyright: {\textcopyright} 1979 Association for Computing Machinery. All rights reserved.; 11th Annual ACM Symposium on Theory of Computing, STOC 1979 ; Conference date: 30-04-1979 Through 02-05-1979",

year = "1979",

month = apr,

day = "30",

doi = "10.1145/800135.804418",

language = "English (US)",

pages = "237--248",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - The pebbling problem is complete in polynomial space

AU - Gilbert, John E.

AU - Lengauer, Thomas

AU - Tarjan, Robert Endre

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 - https://www.scopus.com/pages/publications/84915686212

UR - https://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 -

The pebbling problem is complete in polynomial space

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this