Author: Ricardo Gibert
Date: 18:15:21 05/09/01
Go up one level in this thread
On May 09, 2001 at 20:34:28, Robert Hyatt wrote: >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... Infinite is not a member of the set of real numbers or of the set integers. A number can tend toward infinity, but cannnot be infinite. If you read "y = x*x, where x and y are members of the set of reals", then x is unbounded and y can be shown to be have a lower bound of zero and no upper bound. The equation y = x*x should be interpreted more formally as "for all x, there exists a y sth y = x*x". Note that in all of the above the variables x & y remain uninstantiated. Indeed, they are univerally and existentionally quantified respectively. When you read the definition of big-O, n is both unbounded and uninstantiated. When you try to apply the definition to chess n is both constant and necessarily bounded. In fact, chess is played on an 8*8 board, so n is 8, which is both an upper bound and a lower bound just like any other constant scalar. Now if I generalize the game of chess to an n*n board, where n is non-specific *and* unbounded, then I can say that solving chess is O(exp(n)). Usually, such a generalization is assumed, but in chess if it is not 8*8, then it is not really chess. In such a case, it is correct to make the generalization explicitly to remain formal. Informally, you can get away with murder. PS: I just noticed an error I have been making. In the big-O definition, n is understood to have a lower bound of zero, but no upper bound, since n<0 is meaningless. Careless! Fortunately, it does not change anything substantively. > > > >> >> >>> >>>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.