Author: Dann Corbit
Date: 10:54:09 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:48:45, Andrew Dados wrote:
[snip]
>I see no need getting sarcastic here.
You are right, I was out of line (again).
>There sure are finite number of cities, but the travelling salesman problem
>*scales*, while chess don't. Each salseman problem is independant and number of
>cities is not bounded. Chess is a one-time problem; if you solve it, then you
>solved all chess positions.
There is no difference. The number of cities on the earth is a constant. If it
were to expand a trillion fold, it is still a constant.
>I think one should not confuse finite chess problem with minimax algorithm which
>can be applied to unbound problems as well as to chess.
All problems have practical applications. That has nothing to do with the
performance behavior of the algorithms.
Chess is exponential. Sorting using comparisons is O(n*log(n)) {actually,
theoretically, it could be improved to O(log(n!)}. TSP is (so far) NP, despite
the fact that there are only a few thousand cities on the earth.
If anything, TSP is far easier than chess, but you don't see anyone claiming
that it is in P, much less O(1)
!
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.