Phutball Endgames are Hard

Simple item page
dc.creatorDemaine, Erik D.
dc.creatorDemaine, Martin L.
dc.creatorEppstein, David
dc.date2000-08-23
dc.date2001-07-27
dc.date.accessioned2026-07-07T03:16:29Z
dc.date.available2026-07-07T03:16:29Z
dc.descriptionWe show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.
dc.description9 pages, 8 figures. Revised to include additional references on the complexity of checkers
dc.identifierhttps://arxiv.org/abs/cs/0008025
dc.identifierhttp://arxiv.org/abs/cs/0008025
dc.identifierMore Games of No Chance, MSRI Publications 42, 2002, pp. 351-360
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30373
dc.subjectComputational Complexity
dc.subjectComputer Science and Game Theory
dc.subjectF.1.3,K.8.0
dc.titlePhutball Endgames are Hard
dc.typetext

Files

Collections

arXiv