Complexity of path discovery game problems

DOI10.1016/S0304-3975(99)00331-XzbMath0939.68051MaRDI QIDQ1566737

Hiroaki Tohyama, Akeo Adachi

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Computing a perfect strategy for nxn chess requires time exponential in n
• Symmetric space-bounded computation
• Space-bounded reducibility among combinatorial problems
• On the complexity of some two-person perfect-information games
• N by N Checkers is Exptime Complete
• Provably Difficult Combinatorial Games
• Classes of Pebble Games and Complete Problems
• A Combinatorial Problem Which Is Complete in Polynomial Space

This page was built for publication: Complexity of path discovery game problems