Author: David Blackman
Date: 21:01:21 05/07/01
Go up one level in this thread
On May 06, 2001 at 21:51:58, Robert Hyatt wrote: >On May 06, 2001 at 18:22:06, Jesper Antonsson wrote: > >>On May 06, 2001 at 10:16:01, Robert Hyatt wrote: >>>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... >> >>This is the first time I have heard someone call an *algorithm* NP. I think you >>should study the definition again, you seem to use it interchangeably with >>"exponential". > > >No. I just use the NP class to hold all cases that can be proven to _not_ >be in deterministic polynomial time. This is not the normal meaning of NP. Most experts in the field use NP to mean, "solveable in Polynomial time on a Non-deterministic Turing machine". So NP includes all of the things that can be done in deterministic polynomial time, and possibly some harder problems as well (but that hasn't been proved). There are surprisingly few problems that have been proved to need exponential time, and even fewer that are of practical interest. There is a huge grey area of problems that apparently need exponential time with the best currently known algorithms, but have not been proven to need exponential time. It might be time to re-read Garey and Johnson. >And trees can certainly be proven to >not be in that class, from the simply formula for nodes searched using either >minimax or alpha/beta... Trees are not the only way to do chess. For instance DAGs could be used instead. And we really don't know if there is some radically different and possibly faster way to do chess.
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.