Author: Robert Hyatt
Date: 17:34:28 05/09/01
Go up one level in this thread
On May 09, 2001 at 19:23:45, Ricardo Gibert wrote: >On May 09, 2001 at 18:16:48, Dann Corbit wrote: > >>Some people are insisting that finite inputs mean O(1). >> >>My insistence is that the big-O behavior should model the difference from n to >>n+1 and from n to n-1 (past some point n0). > > >Definition: f(n) = O(g(n)) (read as "f of n equals big oh of g of n") iff there >exists two positive constants c and n_0 sth |f(n)| <= c*|g(n)| for all n >= n_0. > >I see nothing in the above definition that talks about "n to n+1 and from n to >n-1". > >I do see that n is unbounded. I also note that in chess, n *is* bounded unless >you generalize 8*8 chess to n*n chess when n is then unbounded. If you make such >a generalization, you can conclude that n*n chess is O(exp(n)). You can then >instantiate it to the 8*8 case to obtain a usable result, but please do not say >that 8*8 chess is O(exp(n)) rather than say n*n chess is O(exp(n)). >I don't see this can be made more clear. I'm really at a loss as to why you >cannot interpret formal definitions correctly. I have said this before: Chess is _not_ finite unless you can prove it is a won game for one side. If you can't find a forced mate, it is _definitely_ unbounded as we can play on and on and on shuffling pieces. The rules of the game allow that. If you use your definition, then every hard algorithm is O(1). IE weather forecasting. I am sure that the people at NCAR or EMWF would love to know that since they have spent so much money on Cray's to do weather prediction. And atmospheric modeling is _definitely_ bounded as there is no reason to go to a sampling resolution smaller than the atomic level. By your definition _all_ hard problems are O(1) if you can't prove that they are unbounded or have the potential to have infinite inputs. I can't think of a single hard (reasonable) problem that isn't bounded in some twisted way. By the number of states of each atom in the universe assuming you try to use some quantum state for information storage, for example. There is _always_ a limit to computability, since the infinite case is totally uninteresting... I don't see why we keep going round and round when Dann and I have both cited books with definite statements about complexity applied to trees. Your definition is simply useless since it negates any discussion about complexity for any _real_ problem. Yet we _definitely_ care about what happens to runtime when we have 10x as much data... > > >> >>There are no real algorithms with infinite inputs. These so-called algorithms >>can never terminate. > > >I never said anything about infinite inputs. "Unbounded" is not the same as >"infinite". Get the terminology straight or you will get nowhere. You are defining unbounded as "could be infinite". Or "must eventually be infinite". There is no "unbounded" word in my books on complexity when talking about complexity. Because they are usually talking about "if I can do N cities in 1 week of computation, how long will N+1 cities take?" There is no mention of N+1 where that approaches infinity. That is the context every book I have discusses complexity in... > > >> >>Because we cannot agree on definitions we can never come to an agreement. My >>definitions are the classiscal defintions used in all the literature. The >>alternative definitions make for interesting debate, but since they have no >>value at predictions, they have no practical value.
This page took 0 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.