Author: Jeremiah Penery
Date: 02:42:08 05/09/01
Go up one level in this thread
On May 09, 2001 at 03:39:42, Uri Blass wrote: >On May 09, 2001 at 01:11:50, Dann Corbit wrote: > >>On May 09, 2001 at 00:41:38, Uri Blass wrote: >>[snip] >>>No >>>Chess is clearly polynomial and even O(1) like every solvable problem that is a >>>practical problem. >>> >>>You need constant time to solve chess when the problem is only that the constant >>>is large. >>> >>>The only problems that are exponential are problems when the size of the input >>>has no finite upper bound. >>>You can see the input of every practical problem in the world as something that >>>has an upper bound so saying that an algorithm is not O(1) has only mathematical >>>meaning and not practical meaning. >> >>Unbelievable that you also do not understand Big-O notation. > >I responded to the sentence of Hyatt: >"In the case of chess it is clearly exponential, which is _not_ any form of a >polynomial." > >I did not say that O(1) is not also O(exp(n)). >I understand from the sentence of Hyatt that chess is not O(1) and even not >O(n^500000) If I understand this correctly, a minimax search of the chess tree should be something like O(36^n), where n is the search depth. Of course for most programs of today, perhaps this can be reduced to O(3^n) or so by introducing the errors of selective search. I've had very little work with big-O notation, but I did read a couple of the links given by Dann. Someone please correct me if the above is wrong. :) ><snipped> >>I suggest that you read my other posts on the topic. >> >>Anyone who says that an O(1) process is not O(exp(n)) does not know what the >>notation means!!! >> >>Anyway, you can say what O(f(n)) is by looking only at the algorithms not the >>data. Do you really understand this!? > >I understand what you mean but >Every algorithm when there is a bound on the size of the data is practically >O(1) because exp(constant) is another constant. > >Algorithms to solve problem like sort can be described theoretically >as not O(1) because there is not a finite upper bound for the number of elemnts >by definition. Yes, theoretically you can give infinite elements, but that's really a pointless exercise. An infinite number of elements in any algorithm should take infinite time - that's what makes it infinite. If you divide infinity by 1000000000, it's still infinity. You can theoretically give an infinite-size tree to a tree-searching algorithm too - like the algorithms in chess programs... So tree-search algorithms aren't O(1) (by your definition!), yet chess algorithms are? >For practical purposes you can say that there is a finite upper bound so you can >say that Solving the practical problems can be done in O(1) when the only >problem is the constant. > >Algorithms to solve problem like chess,go or other games can be described as >O(1). I think that's sort of like wiggling through a loophole in the notation. The constant term would be so huge it may as well be infinity, for practical purposes. It's very possible that to solve chess you'd need more material than exists in the universe just to store the information, so again it's a pointless argument.
This page took 0.01 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.