Difference between revisions of "P=NP"
(a proposed solution must be published in a refereed mathematics publication) |
|||
| Line 1: | Line 1: | ||
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 <math>Cn^k</math> 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. | 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 <math>Cn^k</math> 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. | ||
| + | |||
| + | * Before consideration, a proposed solution must be published in a refereed mathematics publication of worldwide repute (or such other form as the SAB shall determine qualifies), and it must also have general acceptance in the mathematics community two years after. [http://www.claymath.org/millennium/Rules_etc/ Clay Mathematics Institute] | ||
==Links== | ==Links== | ||
Revision as of 23:52, 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Cn^k} 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.
- Before consideration, a proposed solution must be published in a refereed mathematics publication of worldwide repute (or such other form as the SAB shall determine qualifies), and it must also have general acceptance in the mathematics community two years after. Clay Mathematics Institute
Links
- P vs NP Problem - Clay Mathematics Institute
- Eight Signs A Claimed P?NP Proof Is Wrong - Technology Review - Friday, August 13, 2010