Author: Dann Corbit
Date: 15:09:38 05/09/01
Go up one level in this thread
On May 09, 2001 at 18:06:36, Uri Blass wrote: >On May 09, 2001 at 17:40:16, Dann Corbit wrote: > >>On May 09, 2001 at 17:32:27, Ricardo Gibert wrote: >>[snip] >>References: A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for >>n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, >>Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A >>31 (1981) 199-214. >> >>FCOL > >The dimension of the board here is a variable and the problem of solving chess >means to 8*8. > >Here n is not bounded so you can say that it is not O(1) and even exponential. > >You can say that from computer's point of view n is bounded because the computer >has not enough memory for very big numbers but the bound is so big that for >practical purpose we can assume that n is not bounded. Consult ANY text on NP problems. Chess will be listed as a classic example.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.