(New page: (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...) |
|||
| Line 3: | Line 3: | ||
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? | 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? | ||
| − | |||
--[[ysuo_MA375Fall2008walther]] | --[[ysuo_MA375Fall2008walther]] | ||
Revision as of 11:06, 23 November 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?
