Author: Robert Hyatt
Date: 13:24:02 05/09/01
Go up one level in this thread
On May 09, 2001 at 14:08:10, Ricardo Gibert wrote: >On May 09, 2001 at 14:04:55, Eugene Nalimov wrote: > >>Uri, there is branch of the mathematics (not even computer science, just >>ordinary mathematics) that studies the complexity of algorithms. Algorithms were >>used in mathematics long before computers appeared, for example GCD algorithm >>was known to the classic greeks. >> >>*Very* rude explanation of big-O notation is: you have the algorithm that >>require M operations (or steps, or machine instructions, or clock cycles, etc.) >>when input in N elements long. You are increasing length of the input; how much >>operations will be necessary now? That has *nothing* to do with the fact that >>majority of practically used algorithms will terminate in finite number of steps >>when input is finite. >> >>Eugene > > >But the the length of the input does not increase and that's the whole point. > But it does. From 38^1, to 38^2, to 38^3, ... to 38^N where N is huge. There is no linear relationship to express that cost per additional ply. There is no polynomial either. And it can not be done with an NP algorithm either. You say chess is finite. I say it isn't. Until the FIDE rules are changed, it _clearly_ is not finite.
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.