Author: Dann Corbit
Date: 09:39:23 05/09/01
Go up one level in this thread
On May 09, 2001 at 10:48:15, Ricardo Gibert wrote:
[snip]
>>hope you are right also. Of course, the discovery of such an algorithm will
>>*still* mean that chess is O(exp(n)), for those that know what the term means.
>>-- wink, wink.
>
>But in chess, n is constant. Chess is O(1). If O(exp(n)) were correct, then
>there would not exist a constant c sth exp(n) = c*(1). Clearly such a constant
>exists, so you are mistaken. If the size of the chessboard were not limited to
>8x8, then O(exp(n)) would make sense.
Of course, if such an analysis were correct then you would be agreeing with me,
because O(1) is a microscopic subset of O(exp(n)).
On the other hand, O(1) is easily computable. What's the answer, then?
All of algorithm analysis would be completely useless using this sort of vacuous
reasoning.
Will you really sort with an arbitrary number of inputs? Can you cram in more
than an unsigned 64 bit integer of elements? (or 256 bit integer or one
trillion bit integer)... If not, then it's BOUNDED and (by golly) O(1) {by the
'if it is bounded it must be O(1) school of thought'}.
I really can't believe so many smart people don't understand it. It must be the
educational systems, because there are reams of folks who seem to think this
way.
Even if you disagree with me, then you agree with me. If a problem is O(1) then
BY DEFINITION it is O(exp(n)). Hence, you can only agree. But knowing a lid is
only important if that lid makes the problem practically computable. With
chess, if we ground the earth into powder for storage and computed until the sun
went out for time we would not even be approaching the answer. If you call that
O(1), I don't want you designing any algorithms for me.
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.