Author: Robert Hyatt
Date: 07:07:06 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) > You understood correctly. ><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. This is not the definition of bit-Oh. It is a notation that tells you how hard you have to work as you increase the number of inputs. If the work increases linearly with the inputs, it is a linear function. If it increases exponentially with the number of inputs it is an exponential function. > >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. That would be true of _any_ algorithm and would make big-Oh notation worthless. We just say everything is O(1) because _no_ algorithm can terminate when given an infinite number of input values. > >Algorithms to solve problem like chess,go or other games can be described as >O(1). > >Uri Only by someone that hasn't had a complexity theory class.
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.