Millennium Prize Problems: Difference between revisions
Mindmatrix (talk | contribs) m Reverted edits by 86.131.125.200 (talk) to last version by 65.110.255.173 |
Soulweaver (talk | contribs) m →P versus NP: fix subsection link |
||
| Line 16: | Line 16: | ||
===P versus NP=== |
===P versus NP=== |
||
{{Main|P versus NP problem}} |
{{Main|P versus NP problem}} |
||
The question is whether, for all problems for which an algorithm can ''verify'' a given solution quickly (that is, in [[Polynomial time#Polynomial time|polynomial time]]), an algorithm can also ''find'' that solution quickly. The former describes the class of problems termed NP, while the latter describes P. The question is whether or not all problems in NP are also in P. This is generally considered one of the most important open questions in [[mathematics]] and [[computation|theoretical computer science]] as it has far-reaching consequences to other problems in [[mathematics]], and to [[biology]], [[philosophy]]<ref>{{cite web |url=http://eccc.hpi-web.de/report/2011/108/ |title=Why Philosophers Should Care About Computational Complexity |date=14 August 2011 |author=[[Scott Aaronson]]|publisher=Technical report}}</ref> and [[cryptography]] (see [[P versus NP problem#Consequences of |
The question is whether, for all problems for which an algorithm can ''verify'' a given solution quickly (that is, in [[Polynomial time#Polynomial time|polynomial time]]), an algorithm can also ''find'' that solution quickly. The former describes the class of problems termed NP, while the latter describes P. The question is whether or not all problems in NP are also in P. This is generally considered one of the most important open questions in [[mathematics]] and [[computation|theoretical computer science]] as it has far-reaching consequences to other problems in [[mathematics]], and to [[biology]], [[philosophy]]<ref>{{cite web |url=http://eccc.hpi-web.de/report/2011/108/ |title=Why Philosophers Should Care About Computational Complexity |date=14 August 2011 |author=[[Scott Aaronson]]|publisher=Technical report}}</ref> and [[cryptography]] (see [[P versus NP problem#Consequences of solution|P versus NP problem proof consequences]]). |
||
:''"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps,' no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..." |
:''"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps,' no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..." |
||
Revision as of 05:07, 3 November 2014
 | This article needs additional citations for verification. (January 2013) |
| Millennium Prize Problems |
|---|
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. As of October 2014, six of the problems remain unsolved. A correct solution to any of the problems results in a US $1,000,000 prize (sometimes called a Millennium Prize) being awarded by the institute. The Poincaré conjecture was solved by Grigori Perelman, but he declined the award in 2010.
Solved problems
Poincaré conjecture
In topology, a sphere with a two-dimensional surface is characterized by the fact that it is compact and simply connected. The Poincaré conjecture is that this is also true in one higher dimension. The question had been solved for all other dimensions. The conjecture is central to the problem of classifying 3-manifolds.
The official statement of the problem was given by John Milnor.
A proof of this conjecture was given by Grigori Perelman in 2003; its review was completed in August 2006, and Perelman was selected to receive the Fields Medal for his solution but he declined that award.[1] Perelman was officially awarded the Millennium Prize on March 18, 2010,[2] but he also declined the award and the associated prize money from the Clay Mathematics Institute. The Interfax news agency quoted Perelman as saying he believed the prize was unfair. Perelman told Interfax he considered his contribution to solving the Poincare conjecture no greater than that of Columbia University mathematician Richard Hamilton.[3]
Unsolved problems
P versus NP
The question is whether, for all problems for which an algorithm can verify a given solution quickly (that is, in polynomial time), an algorithm can also find that solution quickly. The former describes the class of problems termed NP, while the latter describes P. The question is whether or not all problems in NP are also in P. This is generally considered one of the most important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, and to biology, philosophy[4] and cryptography (see P versus NP problem proof consequences).
- "If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps,' no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..."
- — Scott Aaronson, MIT [5]
Most mathematicians and computer scientists expect that P ≠ NP.[6]
The official statement of the problem was given by Stephen Cook.
Hodge conjecture
The Hodge conjecture is that for projective algebraic varieties, Hodge cycles are rational linear combinations of algebraic cycles.
The official statement of the problem was given by Pierre Deligne.
Riemann hypothesis
The Riemann hypothesis is that all nontrivial zeros of the analytical continuation of the Riemann zeta function have a real part of 1/2. A proof or disproof of this would have far-reaching implications in number theory, especially for the distribution of prime numbers. This was Hilbert's eighth problem, and is still considered an important open problem a century later.
The official statement of the problem was given by Enrico Bombieri.
Yang–Mills existence and mass gap
In physics, classical Yang–Mills theory is a generalization of the Maxwell theory of electromagnetism where the chromo-electromagnetic field itself carries charges. As a classical field theory it has solutions which travel at the speed of light so that its quantum version should describe massless particles (gluons). However, the postulated phenomenon of color confinement permits only bound states of gluons, forming massive particles. This is the mass gap. Another aspect of confinement is asymptotic freedom which makes it conceivable that quantum Yang-Mills theory exists without restriction to low energy scales. The problem is to establish rigorously the existence of the quantum Yang-Mills theory and a mass gap.
The official statement of the problem was given by Arthur Jaffe and Edward Witten.
A claimed solution by South Korean researchers in 2013 was deemed insufficient.[7]
Navier–Stokes existence and smoothness
The Navier–Stokes equations describe the motion of fluids. Although they were found in the 19th century, they still are not well understood. The problem is to make progress toward a mathematical theory that will give insight into these equations.
The official statement of the problem was given by Charles Fefferman.
Birch and Swinnerton-Dyer conjecture
The Birch and Swinnerton-Dyer conjecture deals with a certain type of equation, those defining elliptic curves over the rational numbers. The conjecture is that there is a simple way to tell whether such equations have a finite or infinite number of rational solutions. Hilbert's tenth problem dealt with a more general type of equation, and in that case it was proven that there is no way to decide whether a given equation even has any solutions.
The official statement of the problem was given by Andrew Wiles.
See also
- Hilbert's problems
- List of unsolved problems in mathematics
- Paul Wolfskehl (offered a cash prize for the solution to Fermat's Last Theorem)
- Smale's problems
References
- ^ "Maths genius declines top prize". BBC News. 22 August 2006. Retrieved 16 June 2011.
- ^ "Prize for Resolution of the Poincaré Conjecture Awarded to Dr. Grigoriy Perelman" (PDF) (Press release). Clay Mathematics Institute. March 18, 2010. Retrieved March 18, 2010.
The Clay Mathematics Institute (CMI) announces today that Dr. Grigoriy Perelman of St. Petersburg, Russia, is the recipient of the Millennium Prize for resolution of the Poincaré conjecture.
- ^ "Russian mathematician rejects million prize - Boston.com".
{{cite news}}: Unknown parameter|deadurl=ignored (|url-status=suggested) (help) [dead link] - ^ Scott Aaronson (14 August 2011). "Why Philosophers Should Care About Computational Complexity". Technical report.
- ^ Scott Aaronson (4 September 2006). "Reasons to believe". Retrieved 8 October 2014.
- ^ William I. Gasarch (June 2002). "The P=?NP poll" (PDF). SIGACT News. 33 (2): 34–47. doi:10.1145/1052796.1052804.
{{cite journal}}: Cite has empty unknown parameter:|1=(help) - ^ Yablon, Jay R. (December 5, 2013). "Brief Comment on "Dimensional Transmutation by Mono pole Condensation in QCD"" (PDF). vixra.org. Retrieved 4 August 2014.
- This article incorporates material from Millennium Problems on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
Further reading
- Devlin, Keith J. (2003) [2002]. The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time. New York: Basic Books. ISBN 0-465-01729-0.
- Carlson, James; Jaffe, Arthur; Wiles, Andrew, eds. (2006). The Millennium Prize Problems. Providence, RI: American Mathematical Society and Clay Mathematics Institute. ISBN 978-0-8218-3679-8.
External links
