Difference between revisions of "P=NP"
(MIT says it's still unsolved) |
(Clay Mathematics Institute also has a description of the problem ... a little easier to read, if I may say so) |
||
| Line 2: | Line 2: | ||
==Links== | ==Links== | ||
| + | *[http://www.claymath.org/millennium/P_vs_NP/ P vs NP Problem] - Clay Mathematics Institute | ||
*[http://www.technologyreview.com/blog/post.aspx?bid=349&bpid=25616 Eight Signs A Claimed P?NP Proof Is Wrong] - ''Technology Review'' - Friday, August 13, 2010 | *[http://www.technologyreview.com/blog/post.aspx?bid=349&bpid=25616 Eight Signs A Claimed P?NP Proof Is Wrong] - ''Technology Review'' - Friday, August 13, 2010 | ||
[[Category:Mathematics]] | [[Category:Mathematics]] | ||
Revision as of 23:25, August 15, 2010
Whether P=NP is an unsolved problem in computer science. Informally, the problem asks if all problems whose solutions can be checked quickly can have those solutions found quickly. More formally, a collection of yes or no questions is a said to be in P if there exists a Turing machine T, an integer k and constant C such that which which will correctly answer whether the answer is yes or no, and the Turing machine will always terminate after a number of steps bounded by where n is the length of the input. A problem is said to be in NP if the same holds true for a non-deterministic Turing machine. It is not hard to see that any problem in P is also in NP. It is unknown if P=NP or not. This problem is one of the seven Millennium problems which each have a million dollar prize.
Links
- P vs NP Problem - Clay Mathematics Institute
- Eight Signs A Claimed P?NP Proof Is Wrong - Technology Review - Friday, August 13, 2010