Author: Jesper Antonsson
Date: 15:10:30 05/15/01
Go up one level in this thread
On May 15, 2001 at 13:06:09, Robert Hyatt wrote:
>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.
Does the big O definition say anything about what's doable in your universe?
>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.
Not 20->21, but perhaps 200-201, and certainly with 6000->6001. And this
algorithm can be constructed, you know that and I know that. That it hasn't been
done isn't relevant.
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.