Author: Robert Hyatt
Date: 10:06:09 05/15/01
Go up one level in this thread
On May 15, 2001 at 06:40:58, Martin Schubert wrote:
>On May 14, 2001 at 15:51:29, Robert Hyatt wrote:
>
>>On May 14, 2001 at 15:05:27, Uri Blass wrote:
>>
>>>On May 14, 2001 at 13:58:50, Robert Hyatt wrote:
>>>
>>><snipped>
>>>>As far as the "mythical" requirement that N be unbounded, I give this explicit
>>>>definition of Big-oh:
>>>>
>>>>"We say a function g(n) is O(f(n)) for another f(n) if there exist constants
>>>>c and N such that for all n>=N, we have g(n) <= cf(n).
>>>>
>>>>I don't see any _requirement_ that n or N be unbounded.
>>>
>>>
>>>
>>>
>>>If n is bounded and gets only a finite number of values then it is clear that
>>>always g(n) is O(1) by this definition
>>>
>>>In this case g(n) can get only a finite number of values and
>>>you can define c=max({g(n)}
>>>You get g(n)<=c for all n>=1 and it means by definition that g(n)=O(1).
>>>
>>>Uri
>>
>>That is simply an interpretation. As I said, give me a citation that _requires_
>>that N be unbounded. Since no _real_ algorithm can have unbounded input. The
>>traveling salesman problem is one example. If we define a city as the space
>>occupied by 1 atom, which is the smallest "city" of interest, then that is
>>O(1), yet it is not given as O(1) in any book I have...
>>
>>Since by definition _all_ algorithms have finite input to be useful, they are
>>all O(1) by this perverted definition. Perhaps math people define this
>>differently, but in computational science, we don't consider _all_ algorithms
>>to be O(1) as that definition is useless in the extreme.
>
>O-Notation is never about one specific problem, it's about one "family" of
>problems. If you want to look at the asymptotical behaviour of chess, you need
>an input n, for example the size of the board. Other things don't make sense.
>You can't say, something is O(1) because of something is bounded. First you have
>to define what your "n" is, and then look at the asymptotical behaviour.
>It doesn't matter for example, if you play chess only on a 8x8-board. The
>question is "what would happen if you played on a nxn-board?".
>
>Martin
I'm not interested in NxN. Even though that is a completely bounded game,
since there is a very definite maximum for N due to the size of the universe.
And we are back to where we started. I am not aware of _any_ problem that is
truly unbounded. Which means we don't need any theory work at all, we just
say O(1) and go to the next problem, which ought to be easy to solve at O(1)
complexity.
All I care about is that in 8x8 chess, for each additional ply of depth I try
to do, I get an exponential increase in the work required to do the search.
For all depth N that are doable in the universe I live within.
So I will continue to say that N+1 is hard, while some will say it is O(1).
I'm waiting to see their algorithm however, that will search to depth=20 and
depth=21 in the same amount of time.
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.