Author: Dann Corbit
Date: 10:23:25 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:18:52, Uri Blass wrote: >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). This is simply wrong. I guess we are at an impasse. >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. Show me any algorithms book that says any sorting algorithm is O(1). This is nonesense of astronomical proportion. And exactly the sort of thing we arrive at when we make silly assumptions to start with.
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.