Author: Jesper Antonsson
Date: 03:36:40 05/06/01
Go up one level in this thread
On May 05, 2001 at 23:10:20, Robert Hyatt wrote: >On May 05, 2001 at 21:13:15, Jesper Antonsson wrote: >>On May 04, 2001 at 22:05:51, Robert Hyatt wrote: >>>Second, a tree search such as minimax is already known (and proven) to be NP. >> >>So, Tic-Tac-Toe (which can also be solved with minimax) is NP? Hardly. > >Yes it is, in fact. If it has a tree shape, it is NP by definition. NP >doesn't mean specific instance problems are not solvable... 1. It is possible to write bad algorithms that solve polynomial problems in exponential time, with "tree shapes". That doesn't make them NP. 2. What is a larger instance of the "tic-tac-toe problem"? Before you claimed that the exponentiality existed as a function of search depth. Increase the search depth in the mini-max beyond nine in tic-tac-toe, and your search won't take longer time. *It has an upper time bound.* There is a similar limit in chess, it is just too large for us to ever attain.
This page took 0.05 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.