2008 | OriginalPaper | Buchkapitel
Parameterized Chess
verfasst von : Allan Scott, Ulrike Stege
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It has been suggested that the parameterized complexity class AW[*] is the natural home of
k
-move games, but to date the number of problems known to be in this class has remained small. We investigate the complexity of
Short Generalized Chess
—the problem of deciding whether a chess player can force checkmate in the next
k
moves. We show that this problem is complete for AW[*].