Author: Ricardo Gibert
Date: 10:07:20 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?
>;-)
>
>>If we were to allow the size of the chessboard to expand, then the
>>number of steps in its solution would be NP (extremely likely, but not certain!)
>
>{Not you too!}
>
>WHAT UTTER POPPYCOCK. Please provide a citation from a reputable source that
>says if we have a bound on the data our algorithm becomes O(1).
In all the definitions you refer to in the links you gave, n is clearly given as
unbounded.
The notation O(f(n)) is used to describe the asymptotic behavior for
sufficiently large n as n increases. This is crystal clear from the citations
You give above.
It makes no sense to speak of the asymptotic behavior of an algorithm as n
increases when n is in fact constant as it is in chess.
That's so
>nonesensical that it renders an analysis of algorithsm as completely pointless.
>ALL INPUTS ARE BOUNDED!!!!!
Of course they are bounded in a specific instantiation of a problem where n is
unbounded, but they are not bounded (at least in theory) before the problem is
instantiated.
>
>There is no such requirement anywhere in the literature. The running time of
>the algorithm can be discerned by examination of the algorithm alone. In fact,
>that is how it is always done.
>
Read and understand the very citations you give above more carefully.
[snip]
If I want to find the maximum of 2 integers, I can give an algorithm that is
O(1). This means I can furnish a finite program that does not contain any loops
that will accomplish the task.
If I generalize this problem to n integers, where n is unbounded, then I must
resort to using a loop. The algorithm is then O(n). If n is bounded then I can
write the program without any loops, since I know n <= some constant. The
algorithm is then O(1).
In chess, n is bounded. I can write a finite program (in theory I can) that does
not contain any loops. The running time is O(1). If n is unbounded, no such
program without loops exists, so instead if I use minimax, the running time is
O(exp(n)).
This is all very clear from the citations you give. Please read carefully.
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.