Presentation by Anastasia Onoprienko "NP-Completeness of Hanabi Game with Minimal Parameters"

On December 10, the research seminar "From the Logical Point of View" took place.

Abstract
We study the algorithmic complexity of the cooperative card game Hanabi. The feature of Hanabi is that players see each other’s cards but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters of the game that preserve NP-hardness. If these parameters are further reduced, the game turns out to be solvable in polynomial time.

Keywords: algorithmic game theory, computational complexity, NP-completeness, Hanabi