Hanabi is NP-hard, even for cheaters who look at their cards

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

zbMATH Keywords

computational complexitysortingalgorithmic combinatorial game theorysolitaire games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items

Backgammon is hard, Unnamed Item, The Hanabi challenge: a new frontier for AI research

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