Editing Checkers (section)

== Computational complexity ==
[[Generalized game|Generalized]] Checkers is played on an M × N board.

It is [[PSPACE-hard]] to determine whether a specified player has a winning strategy. And if a polynomial bound is placed on the number of moves that are allowed in between jumps (which is a reasonable generalisation of the drawing rule in standard Checkers), then the problem is in PSPACE, thus it is PSPACE-complete.<ref name="fraenkel19782">{{cite conference|last1=Fraenkel|first1=Aviezri S.|last2=Garey|first2=M. R.|last3=Johnson|first3=David S.|last4=Yesha|first4=Yaacov|year=1978|title=The complexity of checkers on an N × N board|pages=55–64|doi=10.1109/SFCS.1978.36|book-title=19th Annual Symposium on Foundations of Computer Science}}</ref> However, without this bound, Checkers is EXPTIME-complete.<ref>{{cite journal|last1=Robson|first1=J. M.|date=May 1984|title=N by N Checkers is EXPTIME complete|journal=SIAM Journal on Computing|volume=13|issue=2|pages=252–267|doi=10.1137/0213018}}</ref>

However, other problems have only [[polynomial complexity]]:<ref name="fraenkel19782" />

* Can one player remove all the other player's pieces in one move (by several jumps)?
* Can one player king a piece in one move?