Author: Andrew Dados
Date: 11:10:02 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:47:49, Dann Corbit wrote: > >Now, if we accept the "fininte inputs means O(1)" definition, then only and >idiot would argue that all problems are O(1). If all problems are O(1), then >everything is computable. But something is wrong with that picture. > >Divorce the algorithm from the data. >Count the fundamental operations. >Describe these as a function. > >That's what big-O notation boils down to. And if O(f(n)) finds f() to be an >exponential function, then we must keep n small or it is of little use to try >and solve it (worst case). There is no other value to O(f(n)) calculation. > >The definition put forth by some that "fininte inputs means O(1)" is useless. I agree with your last sentence, yes. I would rather say, that 'finite state number of a problem means O(1)'. Or 'if it is solvable once for all (any chess position in our case) then it's O(1). Because we proved there exist a formula computable without loops. We don't know such a formula yet, but we know it exists. For given traveling salesman problem we need those loops as for now. Now, set up an 8-piece position and leave it overnight for Crafty with 5 piece TBs. Would it stay O(exp(n))? Surely no. Most likely you'll get O(1). So already we catching that O(1) tail slowly :) -Andrew-
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.