But that is trivial

Every field has its own share of its-obviously-true-but-insanely-hard-to-prove problems. In complexity theory, it is \( \mathrm{P} \) vs. \( \mathrm{NP} \)1. In number theory, it is the Riemann hypothesis….

But these problems are relatively non-trivial to state. You need an undergrad in CS and respectively math to properly understand these problems (Unless you’re at Waterloo, in which case you need a BMath in CS for the former2. ;p). For instance, \( \mathrm{P} \) vs. \( \mathrm{NP} \) isn’t exactly about verification vs. provability but rather about polynomial deterministic verification vs. deterministic provability. (Yes, the probabilistic version–\( \mathrm{BPP} \) vs. \( \mathrm{MA} \) is also open and so is \( \mathrm{P} \) vs. \( \mathrm{PSPACE} \) but I think you get my point!)

But try this: It is not yet proven that \( e+\pi \) is irrational! To refresh your memory, a rational number is one that can be expressed as \( \frac{p}{q} \) for \( p,q \) being integers and \( \gcd(p,q) = 1 \). But we know due to the wonderful work of Hermite (1973) and Lindemann (1882) that \( e \) and \( \pi \) respectively are transcendental. Again, transcendental means that it is not algebraic over the rationals. For those of you with social lives, it means that it cannot be expressed as a root of a polynomial with rational coefficients. And from this it follows that any real transcendental number is irrational.

For a friendly introduction to the Riemann hypothesis see “A Friendly Introduction to The Riemann Hypothesis” by Thomas Wright. And for \( \mathrm{P} \) vs. \( \mathrm{NP} \), see “The Golden Ticket P, NP, and the Search for the Impossible” by Lance Fortnow3.

  1. A friend of mine recently pointed out to me that I was being insanely cocky by saying “\(\mathrm{P} \neq \mathrm{NP} \) is open” when some giants like Donald Knuth believe otherwise. So, yeah, I will stick to saying \( \mathrm{P} \) vs. \( \mathrm{NP} \) till Ketan Mulmuley finishes sharpening his Algebraic Geometry and Representation Theory tools and kills the hope of all equalists.
  2. For non-Waterloo readers, this is a reference to the fact that you can get a Bachelor of Computer Science from Waterloo without taking any “real CS theory” courses.
  3. Although, I would never consider a world where \( \mathrm{P} = \mathrm{NP} \) to be “Beautiful”.