tag:blogger.com,1999:blog-3722233.post2569629765075395827..comments2022-12-07T02:47:32.514-06:00Comments on Computational Complexity: Checkers- Clarification by SchaeferLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-58767354542865205142007-08-23T02:42:00.000-05:002007-08-23T02:42:00.000-05:00In most instances of the n x n checkers problem, n...In most instances of the n x n checkers problem, n has more than a billion billion digits.<BR/><BR/>So I think there is a flaw in calling the 8x8 problem medium-sized.I. J. Kennedyhttps://www.blogger.com/profile/04805435564360543720noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24365210823204470882007-08-22T14:04:00.000-05:002007-08-22T14:04:00.000-05:00This raises the interesting question of: what, if ...This raises the interesting question of: what, if any, relationship does the problem class in which a generalized problem falls have with finite instances of that problem? We know generalized Checkers is EXPTIME-complete, so there's no polynomial-time solution in terms of the board size, but it's trivial to solve on small boards, and evidently within reach to solve on the medium-size boards that are complex enough to satisfy humans. Does this make it any harder than a game that generalizes to a PSPACE-complete problem? Or should we be comparing the sizes of the state spaces instead?D Coetzeehttps://www.blogger.com/profile/05407492273389264037noreply@blogger.com