Author: Anthony Cozzie
Date: 06:21:39 01/20/05
Go up one level in this thread
On January 20, 2005 at 06:43:18, Oreopoulos Kostas wrote: >Is there a proof the Chess ia actually an Hard NP problem? No. It is worse ;) Basically, in complexity theory there are: P: can be solved in polynomial time (example: find shortest path in a graph) NP: can be VERIFIED in polynomial time. In other words, given a solution I can tell you if it is correct quickly. The classic example of this is finding a solution to a boolean equation. I give you a massive boolean equation, you find me a set of values that cause it to be true. This (currently) cannot be done in polynomial time, but verifying a correct solution is easy. NP-hard: the set of all NP problems that can be reduced to each other by various transformations. It is an open question whether P=NP. However Chess, and the traveling salesman problem belong to an even harder class of problems, exptime, where both the solution and the verification take exponential time. If I give you a sample game and tell you it is a "perfect game", e.g. white wins with 1.d4 and none of black's defenses work, proving I am right is still quite hard. Note that just because a problem is NP or exptime doesn't necessarily make it hard to solve, unless (like Chess) the constants are large enough. anthony P.S. I was always annoyed that no one ever explained this to me, until I figured it out two months ago while studying for the GRE. I think there are legions of undergrads walking around CMU with the idea that "p=easy" and "np=hard". The concept is really pretty simple. Admittedly, I was a ECE major, though.
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.