Author: Robert Hyatt
Date: 07:16:01 05/06/01
Go up one level in this thread
On May 06, 2001 at 06:36:40, Jesper Antonsson wrote: >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. No.. but "minimax" is _definitely_ NP. A linear pattern-matcher (for tic-tac-toe) would not be and it is not hard to write... but minimax... > >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. You are therefore saying that some chess positions are not NP? That is not how NP works. NP is not about how long a solution takes.. it is about how hard it is to go one level deeper (in the case of the tree). It doesn't really matter if some positions have a mate in 2... it is the "general case" that is interesting when you look at NP. Otherwise the traveling salesman problem would not be NP, yet any textbook shows and proves that it is. Even though for 4 cities it is easy to do and there is a finite depth limit for the final solution.
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.