Eleusis: complexity and interaction in inductive inference

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