Author: Jesper Antonsson
Date: 19:03:46 05/05/01
Go up one level in this thread
On May 04, 2001 at 16:15:41, Dann Corbit wrote: >On May 04, 2001 at 15:01:52, Jesper Antonsson wrote: >>Well, I would say that in a formal computer science framework, you are wrong. >>Chess is clearly finite, and thus in polynomial space. Of course, the number of >>nodes in the search tree is exponential in the tree depth, but *only* if you >>don't search deeply enough. (We will probably never be able to search deeply >>enough either, but that is beside the point.) > >Well, the same could be said for the transporation problem. After all, we only >have a finite number of cities. > >It's always pragmatic at some point. We could say that every problem is O(1) >since we always have finite inputs. It's just that the constant multiplier is a >KILLER. >;-) Well, in a sense I can agree with you. On the other hand, in chess, we have an upper bound on time *regardless* of input size (target search depth), which isn't the same as the fact that we have an upper bound on time when the input is fixed. That's why the transportation problem is not O(1) while chess is.
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.