Computer Science

Guess Which Way? | Gödel’s Lost Letter and P=NP


Math problems get solved from time to time. Today I wonder if they are solved the way we guessed they were going to be solved? For example do most feel that P vs NP is likely to be equal or unequal?

William Gasarch has conducted three polls of researchers concerning this question. Confidence that P is not equal NP has been increasing: In 2002 61% believe unequal; in 2012 83% believe unequal; and in 2019 88% believed unequal. When restricted to experts, the 2019 answers became 99% believed unequal.

Many Are Guessed Right Before Being Solved

Consider the famous: 4 color theorem.It states that no more than four colors are required to color the regions of any planar map so that no two adjacent regions have the same color. Most seemed to believe that 4 colors was going to be enough.

False disproofs usually violated the assumptions of the theorem. Such as using a region that consists of multiple disconnected parts, or disallowing regions of the same color from touching at a point. They got the statement of the theorem incorrect. Martin Gardner (1975) played an April Fool’s joke by asserting that the McGregor map consisting of 110 regions required five colors and constitutes a counterexample to the four-color theorem.

Some Guessed Wrong Before Being Solved

The famous Fermat Last Theorem was that there was no positive integer solution to:
x^n + y^n = z^n
with n >2 and xyz not zero.

The link occurred by contemplating the unthinkable—what would happen if Fermat’s Last Theorem was not true? This would mean that there existed a set of solutions to Fermat’s equation, and therefore this hypothetical combination of numbers could be used as the basis for constructing a hypothetical elliptic curve. Ribet demonstrated that this elliptic curve could not possibly be related to a modular form, and as such it would defy the Shimura-Taniyama conjecture.

Running the argument backwards, if somebody could prove the Shimura-Taniyama conjecture then every elliptic curve must be related to a modular form, hence any solution to Fermat’s equation is forbidden to exist, and hence Fermat’s Theorem must be true. If somebody could prove the Shimura-Taniyama conjecture, then this would immediately imply the proof of Fermat’s Last Theorem. By proving one of the most important conjectures of the twentieth century, mathematicians could solve a riddle from the seventeenth century.

Open Problems

Here are two open problems that are not clear which way we should guess. The first is the Riemann Hypothesis and the second is the twin prime conjecture.

For the Riemann Hypothesis we could guess all the zeroes have real part 1/2. But it is not clear if all believe that this is likely to be the case. The twin prime could be the case that there are infinitely many primes p so that p+2 is also prime. But this might be false as some believe?


Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button