1984/05/01 by J. M. Robson · 2 citations
Computer Science · Social Sciences · Economics, Econometrics and Finance · Mathematics · #Artificial Intelligence in Games #Digital Games and Media #Sports Analytics and Performance #Exponential function #PSPACE #Time complexity #Position (finance) #EXPTIME #Mathematics #Function (biology) #Exponential growth #Upper and lower bounds #Exponential time hypothesis #Combinatorics #Discrete mathematics #Polynomial #Computational complexity theory #Computer science #Algorithm
paper · doi:10.1137/0213018
openalex publication_date 1984/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/19
The game of Checkers can easily be generalized to be played on an N by N board and the complexity of deciding questions about positions regarded as a function of N. This paper considers mainly the question of whether a particular player can force a win from a given position and also the question of what is the best move in a given position. Each of these problems is shown to be complete in exponential time. This means that any algorithm to solve them must take time which rises exponentially with respect to some power of N and moreover that they are amongst the hardest problems with such a time bound.For instance if there are any problems solvable in exponential time but not in polynomial space, then these two problems are amongst them.