Eleusis: complexity and interaction in inductive inference

This paper analyzes the computational complexity of the inductive inference game Eleusis. Eleusis is a card game in which one player constructs a secret rule which has to be discovered by the other players. We determine the complexity of various decision problems that arise in Eleusis. We show that on the one hand, many of the problems are solvable in polynomial time whereas on the other hand, the rules of Eleusis allow for secret rules that can force players to face intractable and undecidable problems. Our results show that computational complexity plays a crucial role in the game and has to be taken into account by the players in their strategic considerations. As Eleusis can be seen as a simulation of inductive inference using membership queries, our results also have relevance for interactive approaches to formal learning theory.