Conjecture: Difference between revisions

Line 27:

==Conditional proofs==

Sometimes, a conjecture is called a ''hypothesis'' when it is used frequently and repeatedly as an assumption in proofs of other results. For example, the [[Riemann hypothesis]] is a conjecture from [[number theory]] that — amongst other things — makes predictions about the distribution of [[prime number]]s. Few number theorists doubt that the Riemann hypothesis is true. In fact, in anticipation of its eventual proof, some have even proceeded to develop further proofs which are contingent on the truth of this conjecture. These are called ''[[conditional proof]]s'': the conjectures assumed appear in the hypotheses of the theorem, for the time being.

Sometimes, a conjecture is called a ''[[hypothesis]]'' when it is used frequently and repeatedly as an assumption in proofs of other results. For example, the [[Riemann hypothesis]] is a conjecture from [[number theory]] that — amongst other things — makes predictions about the distribution of [[prime number]]s. Few number theorists doubt that the Riemann hypothesis is true. In fact, in anticipation of its eventual proof, some have even proceeded to develop further proofs which are contingent on the truth of this conjecture. These are called ''[[conditional proof]]s'': the conjectures assumed appear in the hypotheses of the theorem, for the time being.

These "proofs", however, would fall apart if it turned out that the hypothesis was false, so there is considerable interest in verifying the truth or falsity of conjectures of this type.

Line 47:

[[August Ferdinand Möbius|Möbius]] mentioned the problem in his lectures as early as 1840.<ref name="rouse_ball_1960">[[W. W. Rouse Ball]] (1960) ''The Four Color Theorem'', in Mathematical Recreations and Essays, Macmillan, New York, pp 222-232.</ref> The conjecture was first proposed on October 23, 1852<ref name=MacKenzie>Donald MacKenzie, ''Mechanizing Proof: Computing, Risk, and Trust'' (MIT Press, 2004) p103</ref> when [[Francis Guthrie]], while trying to color the map of counties of England, noticed that only four different colors were needed. The [[five color theorem]], which has a short elementary proof, states that five colors suffice to color a map and was proven in the late 19th century;<ref>{{Cite journal|last=Heawood|first=P. J.|date=1890|title=Map-Colour Theorems|journal=Quarterly Journal of Mathematics|location=Oxford|volume=24|pages=332–338}}</ref> however, proving that four colors suffice turned out to be significantly harder. A number of false proofs and false [[counterexample]]s have appeared since the first statement of the four color theorem in 1852.

The four color theorem was ultimately proven in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]]. It was the first major [[theorem]] to be [[computer-assisted proof#Theorems proved with the help of computer programs|proved using a computer]]. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem (i.e., if they did appear, one could make a smaller counter-example). Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this with hundreds of pages of hand analysis, Appel and Haken concluded that no smallest counterexample exists because any must contain, yet do not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by mathematicians at all because the [[computer-assisted proof]] was infeasible for a human to check by hand.<ref>{{Cite journal|last=Swart|first=E. R.|date=1980|title=The Philosophical Implications of the Four-Color Problem|journal=The American Mathematical Monthly|volume=87|issue=9|pages=697–702|doi=10.2307/2321855|issn=0002-9890|jstor=2321855}}</ref> However, the proof has since then gained wider acceptance, although doubts still remain.<ref>{{Cite book|title=Four colors suffice : how the map problem was solved|last=Wilson|first=Robin|publisher=Princeton University Press|year=2014|isbn=9780691158228|edition=Revised color|location=Princeton, New Jersey|pages=216–222|oclc=847985591}}</ref>

The four color theorem was ultimately proven in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]]. It was the first major [[theorem]] to be [[computer-assisted proof#Theorems proved with the help of computer programs|proved using a computer]]. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem (i.e., if they did appear, one could make a smaller counter-example). Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this with hundreds of pages of hand analysis, Appel and Haken concluded that no smallest counterexample exists because any must contain, yet do not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by mathematicians at all because the [[computer-assisted proof]] was infeasible for a human to check by hand.<ref>{{Cite journal|last=Swart|first=E. R.|date=1980|title=The Philosophical Implications of the Four-Color Problem|journal=The American Mathematical Monthly|volume=87|issue=9|pages=697–702|doi=10.2307/2321855|issn=0002-9890|jstor=2321855}}</ref> However, the proof has since then gained wider acceptance, although doubts still remain.<ref>{{Cite book|title=Four colors suffice : how the map problem was solved|last=Wilson|first=Robin|author-link=Robin Wilson (mathematician)|publisher=Princeton University Press|year=2014|isbn=9780691158228|edition=Revised color|location=Princeton, New Jersey|pages=216–222|oclc=847985591}}</ref>

===Hauptvermutung===

Line 84:

===P versus NP problem===

The [[P versus NP problem]] is a major [[List of unsolved problems in computer science|unsolved problem in computer science]]. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer; it is widely conjectured that the answer is no. It was essentially first mentioned in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]]. Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.<ref>Juris Hartmanis 1989, [~~http~~://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf Gödel, von Neumann, and the P = NP problem], Bulletin of the

The [[P versus NP problem]] is a major [[List of unsolved problems in computer science|unsolved problem in computer science]]. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer; it is widely conjectured that the answer is no. It was essentially first mentioned in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]]. Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.<ref>Juris Hartmanis 1989, [https://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf Gödel, von Neumann, and the P = NP problem], Bulletin of the

European Association for Theoretical Computer Science, vol. 38, pp. 101–107</ref> The precise statement of the P=NP problem was introduced in 1971 by [[Stephen Cook]] in his seminal paper "The complexity of theorem proving procedures"<ref>{{Cite book|last=Cook|first=Stephen|author-link=Stephen Cook|year=1971|chapter=The complexity of theorem proving procedures|chapter-url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|title=Proceedings of the Third Annual ACM Symposium on Theory of Computing|pages=151–158|doi=10.1145/800157.805047|isbn=9781450374644|s2cid=7573663}}</ref> and is considered by many to be the most important open problem in the field.<ref>[[Lance Fortnow]], [https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf ''The status of the '''P''' versus '''NP''' problem''], Communications of the ACM 52 (2009), no. 9, pp. 78–86. {{doi|10.1145/1562164.1562186}}</ref> It is one of the seven [[Millennium Prize Problems]] selected by the [[Clay Mathematics Institute]] to carry a US$1,000,000 prize for the first correct solution.

@@ Line 27: / Line 27: @@
 ==Conditional proofs==
-Sometimes, a conjecture is called a ''hypothesis'' when it is used frequently and repeatedly as an assumption in proofs of other results. For example, the [[Riemann hypothesis]] is a conjecture from [[number theory]] that — amongst other things — makes predictions about the distribution of [[prime number]]s. Few number theorists doubt that the Riemann hypothesis is true. In fact, in anticipation of its eventual proof, some have even proceeded to develop further proofs which are contingent on the truth of this conjecture. These are called ''[[conditional proof]]s'': the conjectures assumed appear in the hypotheses of the theorem, for the time being.
+Sometimes, a conjecture is called a ''[[hypothesis]]'' when it is used frequently and repeatedly as an assumption in proofs of other results. For example, the [[Riemann hypothesis]] is a conjecture from [[number theory]] that — amongst other things — makes predictions about the distribution of [[prime number]]s. Few number theorists doubt that the Riemann hypothesis is true. In fact, in anticipation of its eventual proof, some have even proceeded to develop further proofs which are contingent on the truth of this conjecture. These are called ''[[conditional proof]]s'': the conjectures assumed appear in the hypotheses of the theorem, for the time being.
 These "proofs", however, would fall apart if it turned out that the hypothesis was false, so there is considerable interest in verifying the truth or falsity of conjectures of this type.
@@ Line 47: / Line 47: @@
 [[August Ferdinand Möbius|Möbius]] mentioned the problem in his lectures as early as 1840.<ref name="rouse_ball_1960">[[W. W. Rouse Ball]] (1960) ''The Four Color Theorem'', in Mathematical Recreations and Essays, Macmillan, New York, pp 222-232.</ref> The conjecture was first proposed on October 23, 1852<ref name=MacKenzie>Donald MacKenzie, ''Mechanizing Proof: Computing, Risk, and Trust'' (MIT Press, 2004) p103</ref> when [[Francis Guthrie]], while trying to color the map of counties of England, noticed that only four different colors were needed. The [[five color theorem]], which has a short elementary proof, states that five colors suffice to color a map and was proven in the late 19th century;<ref>{{Cite journal|last=Heawood|first=P. J.|date=1890|title=Map-Colour Theorems|journal=Quarterly Journal of Mathematics|location=Oxford|volume=24|pages=332–338}}</ref> however, proving that four colors suffice turned out to be significantly harder. A number of false proofs and false [[counterexample]]s have appeared since the first statement of the four color theorem in 1852.
-The four color theorem was ultimately proven in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]]. It was the first major [[theorem]] to be [[computer-assisted proof#Theorems proved with the help of computer programs|proved using a computer]]. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem (i.e., if they did appear, one could make a smaller counter-example). Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this with hundreds of pages of hand analysis, Appel and Haken concluded that no smallest counterexample exists because any must contain, yet do not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by mathematicians at all because the [[computer-assisted proof]] was infeasible for a human to check by hand.<ref>{{Cite journal|last=Swart|first=E. R.|date=1980|title=The Philosophical Implications of the Four-Color Problem|journal=The American Mathematical Monthly|volume=87|issue=9|pages=697–702|doi=10.2307/2321855|issn=0002-9890|jstor=2321855}}</ref> However, the proof has since then gained wider acceptance, although doubts still remain.<ref>{{Cite book|title=Four colors suffice : how the map problem was solved|last=Wilson|first=Robin|publisher=Princeton University Press|year=2014|isbn=9780691158228|edition=Revised color|location=Princeton, New Jersey|pages=216–222|oclc=847985591}}</ref>
+The four color theorem was ultimately proven in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]]. It was the first major [[theorem]] to be [[computer-assisted proof#Theorems proved with the help of computer programs|proved using a computer]]. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem (i.e., if they did appear, one could make a smaller counter-example). Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this with hundreds of pages of hand analysis, Appel and Haken concluded that no smallest counterexample exists because any must contain, yet do not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by mathematicians at all because the [[computer-assisted proof]] was infeasible for a human to check by hand.<ref>{{Cite journal|last=Swart|first=E. R.|date=1980|title=The Philosophical Implications of the Four-Color Problem|journal=The American Mathematical Monthly|volume=87|issue=9|pages=697–702|doi=10.2307/2321855|issn=0002-9890|jstor=2321855}}</ref> However, the proof has since then gained wider acceptance, although doubts still remain.<ref>{{Cite book|title=Four colors suffice : how the map problem was solved|last=Wilson|first=Robin|author-link=Robin Wilson (mathematician)|publisher=Princeton University Press|year=2014|isbn=9780691158228|edition=Revised color|location=Princeton, New Jersey|pages=216–222|oclc=847985591}}</ref>
 ===Hauptvermutung===
@@ Line 84: / Line 84: @@
 ===P versus NP problem===
 {{main|P versus NP problem}}
-The [[P versus NP problem]] is a major [[List of unsolved problems in computer science|unsolved problem in computer science]]. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer; it is widely conjectured that the answer is no. It was essentially first mentioned in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]].  Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.<ref>Juris Hartmanis 1989, [http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf Gödel, von Neumann, and the P = NP problem], Bulletin of the
+The [[P versus NP problem]] is a major [[List of unsolved problems in computer science|unsolved problem in computer science]]. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer; it is widely conjectured that the answer is no. It was essentially first mentioned in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]].  Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.<ref>Juris Hartmanis 1989, [https://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf Gödel, von Neumann, and the P = NP problem], Bulletin of the
 European Association for Theoretical Computer Science, vol. 38, pp. 101–107</ref> The precise statement of the P=NP problem was introduced in 1971 by [[Stephen Cook]] in his seminal paper "The complexity of theorem proving procedures"<ref>{{Cite book|last=Cook|first=Stephen|author-link=Stephen Cook|year=1971|chapter=The complexity of theorem proving procedures|chapter-url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|title=Proceedings of the Third Annual ACM Symposium on Theory of Computing|pages=151–158|doi=10.1145/800157.805047|isbn=9781450374644|s2cid=7573663}}</ref> and is considered by many to be the most important open problem in the field.<ref>[[Lance Fortnow]], [https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf ''The status of the '''P''' versus '''NP''' problem''], Communications of the ACM 52 (2009), no.&nbsp;9, pp.&nbsp;78–86. {{doi|10.1145/1562164.1562186}}</ref> It is one of the seven [[Millennium Prize Problems]] selected by the [[Clay Mathematics Institute]] to carry a US$1,000,000 prize for the first correct solution.

Conjecture: Difference between revisions

Navigation menu

Search