Classes of Pebble Games and Complete Problems

DOI10.1137/0208046MaRDI QIDQ3862399zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Takumi Kasai, Akeo Adachi, Shigeki Iwata

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

Chinese checkers gameEXP-completenesslog-spaceNP- completenessone-person gamepebble-gamepolynomial timePSPACE-completenessTowers of Hanoivector addition problemwinning strategy

Mathematics Subject Classification ID

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

Cited in

(13)

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

This page was built for publication: Classes of Pebble Games and Complete Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3862399)