Author: Dann Corbit
Date: 16:31:23 05/09/01
Go up one level in this thread
On May 09, 2001 at 19:27:51, Ricardo Gibert wrote: >On May 09, 2001 at 17:40:16, Dann Corbit wrote: > >>On May 09, 2001 at 17:32:27, Ricardo Gibert wrote: >>[snip] >>References: A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for >>n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, >>Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A >>31 (1981) 199-214. >> >>FCOL > >n is clearly finite, but unbounded in the above, so the time required is >exponential. All quite correct. This is a perfect example that makes *my* case. >The authors clearly understand about big-O perfectly. They took the pains to >generalize the problem to n*n chess. They didn't just say chess, because they >understood perfectly that that would not be correct, which is all that I've been >saying. > >It's clear people cannot tell when a variable is bounded or unbounded and what >is meant by finite and infinite and when a variable has been instantiated and >when it has not and what the difference between an instantiated variable and a >constant, etc. And it is clear that people who consider intractible problems to be O(1) are using a set of definitions that are without value.
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.