Author: Uri Blass
Date: 00:39:42 05/09/01
Go up one level in this thread
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) <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. 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). Uri
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.