The Pebbling Problem is Complete in Polynomial Space
From MaRDI portal
Publication:3906416
DOI10.1137/0209038zbMath0456.68045OpenAlexW2076318470MaRDI QIDQ3906416
Thomas Lengauer, John R. Gilbert, Robert Endre Tarjan
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209038
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Discrete mathematics in relation to computer science (68R99)
Related Items
Complexity, appeal and challenges of combinatorial games, Static-memory-hard functions, and modeling the cost of space vs. time, Single-suit two-person card play, A note about \(k\)-DNF resolution, Min Cut is NP-complete for edge weighted trees, Reversible Pebble Game on Trees, Pebbling meets coloring: reversible pebble game on trees, Scheduling series-parallel task graphs to minimize peak memory, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, Cliques enumeration and tree-like resolution proofs, Pebble games for studying storage sharing, On semantic cutting planes with very small coefficients, Playing Savitch and Cooking Games, Two dynamic programming algorithms for which interpreted pebbling helps, Nullstellensatz size-degree trade-offs from reversible pebbling, DAG reversal is NP-complete, Bandwidth and pebbling, Nullstellensatz size-degree trade-offs from reversible pebbling, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
