Classes of Pebble Games and Complete Problems

DOI10.1137/0208046zbMath0426.68021OpenAlexW2064336391WikidataQ56225515 ScholiaQ56225515MaRDI QIDQ3862399

Shigeki Iwata, Takumi Kasai, Akeo Adachi

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0208046

zbMATH Keywords

polynomial timePSPACE-completenesslog-spacewinning strategyTowers of Hanoione-person gameNP- completenessChinese checkers gameEXP-completenesspebble-gamevector addition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05)

Related Items

Alternating tree automata, Gradually intractable problems and nondeterministic log-space lower bounds, Simultaneous (poly-time, log-space) lower bounds, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, Alternating multihead finite automata, Fine-grained Lower Bounds on Cops and Robbers, The complexity of pursuit on a graph, A multiparameter analysis of domino tiling with an application to concurrent systems, A parametric analysis of the state-explosion problem in model checking, Complexity of token swapping and its variants, Complexity of path discovery game problems, Recent results and questions in combinatorial game complexities