Author: Ricardo Gibert
Date: 16:34:35 05/09/01
Go up one level in this thread
On May 09, 2001 at 19:31:23, Dann Corbit wrote: >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. I did not formulate the definition, but I do find it to be of value all the same.
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.