Author: Uri Blass
Date: 10:18:52 05/09/01
Go up one level in this thread
On May 09, 2001 at 11:27:46, Dann Corbit wrote: >On May 09, 2001 at 10:12:30, Ricardo Gibert wrote: > >>On May 09, 2001 at 02:00:25, Dann Corbit wrote: >> >>>For those of you who don't want to perform your own web search, just choose one >>>of these: >>> >>>http://hissa.nist.gov/dads/HTML/bigOnotation.html >>>http://bio5495.wustl.edu/textbook-html/node15.html >>>http://umastr.math.umass.edu/~holden/Math136-99_projects/Amstutz-OBoyle-Petravage/big-o.html >>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html >>>http://classes.monterey.edu/CST/CST338-01/world/BigO.html >>>http://shalim.csustan.edu/~john/Classes/CS3100_DataStructures/Previous_Semesters/1999_04_Fall/Examples/big-O >>> >>>CS:201, FCOL! >> >>Big-O notation is used to describe asymtotic behavior. It commonly used to >>describe the "running time" of an algorithm. If an algorithm is O(f(n)), n is >>understood to be a finite, but *unbounded*. (For some reason, "unbounded" gets >>confused with infinity. This is an error, but let's not get into that. It isn't >>relevant here) >> >>In chess, n in is bounded. This is a critical distinction, that means chess is >>*not* NP. > >GREAT! Then it's computable. What's the answer, win-loss-draw? >;-) I see no point in continuing to argue. The question is simply question of definition. I did not say that it is easy to solve. I use the definition of NP only for problems with n that is not bounded otherwise the mathematical definition say that it is O(1)(there is a constant and the only problem is that it is too large) I can agree that chess is practically O(exp(n)) and not polynomial for practical purposes but it does not change the fact that by mathematical definition it is O(1). You can say that Sorting is also O(1) from theoretical point of view if you look at sorting that is done by a computer. 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.