Author: Dann Corbit
Date: 15:28:21 05/09/01
Go up one level in this thread
On May 09, 2001 at 18:20:59, 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. Here are some references that classify chess as NP. One goes so far as to offer a formal proof: http://www.cs.duke.edu/~dr/1.00s/L37.html http://www.cs.bu.edu/fac/lnd/toc/z/node18.html http://www.glyph.pe.kr/phoenix/AI/AIChess4.htm http://www.cis.ksu.edu/~schmidt/300f00/Lectures/Week3.html http://www.cs.bu.edu/fac/lnd/toc/n-npcom Are they all confused? Or are they simply using the standard definition of P/NP?
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.