Hey, psst—do you want to get rich quick?
Have you exhausted all the other get-rich-quick schemes on the internet?
Do you have absolutely no marketable skills because you pursued a degree that became obsolete
shortly after graduation due to an unstable and rapidly shifting job market, which then
ironically drove you into crushing student-loan debt that compounded with the pressures of
late-stage capitalism to create a predatory cycle of poverty that has ultimately forced
you to desperately scrape the internet for schemes to support yourself financially?
Well boy do I have a scheme for you: it’s called, “solving one of the world’s most
difficult math problems.”
In the year 2000, the Clay Mathematics Institute issued a bounty for seven major math problems,
dead or alive.
Or solved.
These are considered to be the most difficult unsolved problems in mathematics, and a solution
to any one of them carries a prize of one million dollars.
So far, only one of them has been solved—the Poincaré conjecture—so if you have a proof
that every simply connected, closed 3-manifold is homeomorphic to the 3-sphere, that’s
old news, buddy.
Putting that one aside, there are six left, but one of them has gotten significantly more
attention—and failed attempts to solve it—than the rest: it’s called, “P versus NP.”
I want to talk about P versus NP, not only because it’s the only one of these problems
composed of symbols that I had actually seen before, but also because it’s one of the
most consequential problems in computer science, medicine, shipping logistics, and whatever
field of science has to do with building robots that are so good at board games that they’re
not fun anymore.
This is because it’s the problem at the core of problem-solving itself—so yeah,
you can put away your TI-84, you’re not going to get a million dollars by typing a
bunch of numbers into a wildly-overpriced paperweight from 2004.
This is fancy math.
Technically, this problem asks the question, “does P equal NP?”
And before you say, “no, one of them has an N stuck to it, give me my prize money,”
what this question really means is, “can a problem with an easily verifiable answer
also be easily solved?”
If it turns out that it can, and P does equal NP, we would be able to use the proof to literally
cure cancer and hack Jeff Bezos’s bank account at the same time—but we’ll get to that
bit later.
First, I should explain what P and NP stand for here.
P represents all of the problems that can be solved in polynomial time—or, in words
that can be understood by normal people who don’t already know all of this and aren’t
just watching this video to point out all of the mistakes I’m about to make—it represents
all of the problems that can be solved with algorithm in an amount of time that doesn’t
get exponentially longer the bigger they get.
Most basic math problems fall under this category, like, for example, calculating a tip; whether
you’re dealing with a 3 dollar muffin or a 3 million dollar muffin that you’re using
for some very convoluted money-laundering scheme, calculating 20 percent is pretty much
the same process, and your phone could calculate a tip on any muffin—no matter how much money
you’re laundering—pretty much instantaneously.
NP problems, however, are different.
While they can be checked in polynomial time, they can’t necessarily be solved in polynomial
time—that just means that solving them gets exponentially harder the bigger they get.
Take, for example, the traveling salesman problem.
You might remember that we talked about it in this video, where we explained how it’s
the postal service’s biggest obstacle to getting you your week-late Father’s Day
present fifteen minutes faster.
The problem works like this: given a handful of destinations and a certain distance, is
there any way to tell if there’s a route between all of the destinations that’s shorter
than that distance?
Well, it’s easy to check any given answer, since you can just measure the length of the
route, but there’s actually no efficient way to find the correct answer—you just
have to try every possibility until something works, which can take a really long time and
can be really demoralizing for the elves that live inside the delivery drivers’ routing
devices.
Another example of an NP problem would be sudoku: there’s no algorithm for efficiently
solving a sudoku, but if I gave you a sudoku that I had already filled out, you could pretty
quickly check to see if it was right, and then after about two seconds you could tell
me that it was wrong, because I had just written “sudoku” into the boxes over and over
again and I didn’t even spell it right most of the time.
There are some problems that we thought belonged to this category of easily-checked but not
easily-solved—like determining whether a number is prime or not—but then we found
an algorithm for solving them and they ascended to P-status.
So the question is: is there something about these other problems that makes it impossible
for them to join their friends in the “P” party, or are they all theoretically solvable?
Or, in other words, are all checkable problems eventually going to be solvable problems,
or are they fundamentally different in some way?
Well, when you’re dealing with an infinite number of problems, that seems like an unanswerable
question, but it turns out that a bunch of these problems—like the traveling salesman
problem and sudoku—are actually technically the same problem at their core, and this problem
happens to capture the most difficult aspects of NP; this means that if you come up with
a proof for one of these so-called “NP-complete” problems, you can use it to solve everything
else in NP.
You could use it to route packages with 100% efficiency or accelerate our methods for protein-folding…
but you would also break most of our current financial encryption systems, so you’d probably
have to hide that prize money under your mattress.
So, I was going to tell you that once you won a million dollars from solving one of
these problems that you should invest in a quality kitchen knife, but it turns out you
don’t need a million for that.
My least favorite part of cooking used to be the prep: dicing potatoes, mincing garlic,
trimming meat—you know, the knife-y bits.
But then I got this: the Chef’s Knife from our sponsor, Made In.
I sliced some cantaloupe, tried to catch my phone with the hand with the knife, found
out why the box includes a bandaid, sliced some sweet potato, and man was that the most
pleasurable sweet-potato slicing experience I’ve ever had—it just cuts like butter.
That’s because Made In sources the finest materials and partners with renowned craftsmen
to make these kitchen tools and bring them to you, without the markup.
So, rather than buying a $20 knife that you’re going to replace every year, invest in one
that’s made for life, and backed by a lifetime guarantee—it’ll also make your cooking
more fun, fast, and good.
Same goes for pots, pans, bakeware, plates, and everything else Made In sells—it’s
all high quality, durable, and legitimately used by professionals in world famous restaurants
like Alinea and Le Bernardin.
Now’s the best time to invest in your kitchen, as Made In is offering HAI viewers 15% off,
the best discount available anywhere, by going to MadeIn.com/HALF and using the promo code
“HALF.”