Author: Dann Corbit
Date: 13:15:41 05/04/01
Go up one level in this thread
On May 04, 2001 at 15:01:52, Jesper Antonsson wrote: >On May 03, 2001 at 22:04:35, Dann Corbit wrote: >>Neither of which help all that much. Chess is an exponential process. In >>general, such problems are called "intractable" -- in other words, you can't >>solve them. In fact, this is the case with chess. We can only approximate >>solutions, which is usually good enough. >[...] >>If someone can invent a polynomial time chess algorithm, then chess could be >>solved. But I doubt if that will ever happen because chess is not a problem in >>polynomial space. > >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. ;-)
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.