| Line 15: | Line 15: | ||
| − | An example which uses the above idea is | + | An example which uses the above idea is shown at the following site: [http://www.claymath.org/Popular_Lectures/Minesweeper/ Minesweeper to solve P=NP?]. The author shows how the 3-SAT problem can be transformed in polynomial time into a question about the solvability of a Minesweeper board! Therefore, if you could find a general solution to any Minesweeper board in polynomial time, you would be able to solve 3-SAT (which is NP-complete) in polynomial time. |
--[[User:Nclaus|Nathan Claus]] 17:27, 7 December 2008 (UTC) | --[[User:Nclaus|Nathan Claus]] 17:27, 7 December 2008 (UTC) | ||
Revision as of 12:27, 7 December 2008
(Quick overview from Wikipedia):
The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.
In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" (in polynomial time), can the answers themselves also be computed quickly?
A helpful example would be to consider the subset-sum problem, an example of a problem which is "easy" to verify, but whose answer is believed (but not proven) to be "difficult" to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero", can be quickly verified with a few additions. However, finding such a subset in the first place could take much longer. The information needed to verify a positive answer is also called a certificate. Given the right certificates, "yes" answers to our problem can be verified in polynomial time, so this problem is in NP.
An answer to the P = NP question would determine whether problems like the subset-sum problem are as "easy" to compute as to verify. If it turned out P does not equal NP, it would mean that some NP problems are substantially "harder" to compute than to verify.
--Jniederh 18:18, 23 November 2008 (UTC)
One way to think about the problems being in the same situation is to think of a way to solve one problem using another problem. For example, if you could find a way to solve any Hamilton Path problem with some "subset sum" problem (using polynomial time to convert the problem), then you could show that if you could solve the "subset sum" problem in polynomial time, then you could solve the Hamilton Path in polynomial time. --Norlow 23:56, 23 November 2008 (UTC)
An example which uses the above idea is shown at the following site: Minesweeper to solve P=NP?. The author shows how the 3-SAT problem can be transformed in polynomial time into a question about the solvability of a Minesweeper board! Therefore, if you could find a general solution to any Minesweeper board in polynomial time, you would be able to solve 3-SAT (which is NP-complete) in polynomial time.
--Nathan Claus 17:27, 7 December 2008 (UTC)
