Hanabi is NP-hard, even for cheaters who look at their cards
From MaRDI portal
Publication:528493
DOI10.1016/j.tcs.2017.02.024zbMath1371.91026arXiv1603.01911OpenAlexW2594593206MaRDI QIDQ528493
André van Renssen, Marcel Roeloffzen, Matias Korman, Yago Diez, Man-Kwun Chiu, Jean-François Baffier, Valia Mitsou, Yushi Uno
Publication date: 12 May 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.01911
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- UNO is hard, even for a single player
- Computing a perfect strategy for nxn chess requires time exponential in n
- How to Make the Perfect Fireworks Display: Two Strategies forHanabi
- Tetris is Hard, Even to Approximate
- A threshold of ln n for approximating set cover
- GO Is Polynomial-Space Hard
- A Combinatorial Problem Which Is Complete in Polynomial Space
- The Computational Complexity of the Game of Set and Its Theoretical Applications
- Algorithmic Game Theory