1
00:00:00,510 --> 00:00:02,830
Hey, psst—do you want to get rich quick?

2
00:00:02,830 --> 00:00:05,090
Have you exhausted all the other get-rich-quick
schemes on the internet?

3
00:00:05,090 --> 00:00:08,910
Do you have absolutely no marketable skills
because you pursued a degree that became obsolete

4
00:00:08,910 --> 00:00:12,400
shortly after graduation due to an unstable
and rapidly shifting job market, which then

5
00:00:12,400 --> 00:00:15,450
ironically drove you into crushing student-loan
debt that compounded with the pressures of

6
00:00:15,450 --> 00:00:18,680
late-stage capitalism to create a predatory
cycle of poverty that has ultimately forced

7
00:00:18,680 --> 00:00:21,820
you to desperately scrape the internet for
schemes to support yourself financially?

8
00:00:21,820 --> 00:00:25,861
Well boy do I have a scheme for you: it’s
called, “solving one of the world’s most

9
00:00:25,861 --> 00:00:27,699
difficult math problems.”

10
00:00:27,699 --> 00:00:33,469
In the year 2000, the Clay Mathematics Institute
issued a bounty for seven major math problems,

11
00:00:33,469 --> 00:00:34,569
dead or alive.

12
00:00:34,569 --> 00:00:35,670
Or solved.

13
00:00:35,670 --> 00:00:39,809
These are considered to be the most difficult
unsolved problems in mathematics, and a solution

14
00:00:39,809 --> 00:00:43,600
to any one of them carries a prize of one
million dollars.

15
00:00:43,600 --> 00:00:48,620
So far, only one of them has been solved—the
Poincaré conjecture—so if you have a proof

16
00:00:48,620 --> 00:00:52,609
that every simply connected, closed 3-manifold
is homeomorphic to the 3-sphere, that’s

17
00:00:52,609 --> 00:00:54,120
old news, buddy.

18
00:00:54,120 --> 00:00:58,269
Putting that one aside, there are six left,
but one of them has gotten significantly more

19
00:00:58,269 --> 00:01:04,420
attention—and failed attempts to solve it—than
the rest: it’s called, “P versus NP.”

20
00:01:04,420 --> 00:01:08,850
I want to talk about P versus NP, not only
because it’s the only one of these problems

21
00:01:08,850 --> 00:01:12,510
composed of symbols that I had actually seen
before, but also because it’s one of the

22
00:01:12,510 --> 00:01:16,950
most consequential problems in computer science,
medicine, shipping logistics, and whatever

23
00:01:16,950 --> 00:01:20,040
field of science has to do with building robots
that are so good at board games that they’re

24
00:01:20,040 --> 00:01:21,280
not fun anymore.

25
00:01:21,280 --> 00:01:25,600
This is because it’s the problem at the
core of problem-solving itself—so yeah,

26
00:01:25,600 --> 00:01:28,700
you can put away your TI-84, you’re not
going to get a million dollars by typing a

27
00:01:28,700 --> 00:01:31,980
bunch of numbers into a wildly-overpriced
paperweight from 2004.

28
00:01:31,980 --> 00:01:34,050
This is fancy math.

29
00:01:34,050 --> 00:01:38,200
Technically, this problem asks the question,
“does P equal NP?”

30
00:01:38,200 --> 00:01:42,400
And before you say, “no, one of them has
an N stuck to it, give me my prize money,”

31
00:01:42,400 --> 00:01:47,350
what this question really means is, “can
a problem with an easily verifiable answer

32
00:01:47,350 --> 00:01:49,020
also be easily solved?”

33
00:01:49,020 --> 00:01:54,890
If it turns out that it can, and P does equal
NP, we would be able to use the proof to literally

34
00:01:54,890 --> 00:01:59,460
cure cancer and hack Jeff Bezos’s bank account
at the same time—but we’ll get to that

35
00:01:59,460 --> 00:02:00,460
bit later.

36
00:02:00,460 --> 00:02:03,520
First, I should explain what P and NP stand
for here.

37
00:02:03,520 --> 00:02:07,960
P represents all of the problems that can
be solved in polynomial time—or, in words

38
00:02:07,960 --> 00:02:10,879
that can be understood by normal people who
don’t already know all of this and aren’t

39
00:02:10,879 --> 00:02:13,999
just watching this video to point out all
of the mistakes I’m about to make—it represents

40
00:02:13,999 --> 00:02:17,849
all of the problems that can be solved with
algorithm in an amount of time that doesn’t

41
00:02:17,849 --> 00:02:20,719
get exponentially longer the bigger they get.

42
00:02:20,719 --> 00:02:25,849
Most basic math problems fall under this category,
like, for example, calculating a tip; whether

43
00:02:25,849 --> 00:02:29,019
you’re dealing with a 3 dollar muffin or
a 3 million dollar muffin that you’re using

44
00:02:29,019 --> 00:02:33,270
for some very convoluted money-laundering
scheme, calculating 20 percent is pretty much

45
00:02:33,270 --> 00:02:38,139
the same process, and your phone could calculate
a tip on any muffin—no matter how much money

46
00:02:38,139 --> 00:02:39,780
you’re laundering—pretty much instantaneously.

47
00:02:39,780 --> 00:02:42,950
NP problems, however, are different.

48
00:02:42,950 --> 00:02:48,170
While they can be checked in polynomial time,
they can’t necessarily be solved in polynomial

49
00:02:48,170 --> 00:02:53,159
time—that just means that solving them gets
exponentially harder the bigger they get.

50
00:02:53,159 --> 00:02:55,930
Take, for example, the traveling salesman
problem.

51
00:02:55,930 --> 00:02:59,189
You might remember that we talked about it
in this video, where we explained how it’s

52
00:02:59,189 --> 00:03:02,569
the postal service’s biggest obstacle to
getting you your week-late Father’s Day

53
00:03:02,569 --> 00:03:04,290
present fifteen minutes faster.

54
00:03:04,290 --> 00:03:09,530
The problem works like this: given a handful
of destinations and a certain distance, is

55
00:03:09,530 --> 00:03:13,400
there any way to tell if there’s a route
between all of the destinations that’s shorter

56
00:03:13,400 --> 00:03:14,860
than that distance?

57
00:03:14,860 --> 00:03:19,730
Well, it’s easy to check any given answer,
since you can just measure the length of the

58
00:03:19,730 --> 00:03:24,030
route, but there’s actually no efficient
way to find the correct answer—you just

59
00:03:24,030 --> 00:03:28,919
have to try every possibility until something
works, which can take a really long time and

60
00:03:28,919 --> 00:03:33,079
can be really demoralizing for the elves that
live inside the delivery drivers’ routing

61
00:03:33,079 --> 00:03:34,079
devices.

62
00:03:34,079 --> 00:03:37,959
Another example of an NP problem would be
sudoku: there’s no algorithm for efficiently

63
00:03:37,959 --> 00:03:42,660
solving a sudoku, but if I gave you a sudoku
that I had already filled out, you could pretty

64
00:03:42,660 --> 00:03:46,230
quickly check to see if it was right, and
then after about two seconds you could tell

65
00:03:46,230 --> 00:03:49,779
me that it was wrong, because I had just written
“sudoku” into the boxes over and over

66
00:03:49,779 --> 00:03:52,579
again and I didn’t even spell it right most
of the time.

67
00:03:52,579 --> 00:03:56,439
There are some problems that we thought belonged
to this category of easily-checked but not

68
00:03:56,439 --> 00:04:00,329
easily-solved—like determining whether a
number is prime or not—but then we found

69
00:04:00,329 --> 00:04:03,169
an algorithm for solving them and they ascended
to P-status.

70
00:04:03,169 --> 00:04:08,949
So the question is: is there something about
these other problems that makes it impossible

71
00:04:08,949 --> 00:04:13,689
for them to join their friends in the “P”
party, or are they all theoretically solvable?

72
00:04:13,689 --> 00:04:19,519
Or, in other words, are all checkable problems
eventually going to be solvable problems,

73
00:04:19,519 --> 00:04:22,700
or are they fundamentally different in some
way?

74
00:04:22,700 --> 00:04:27,390
Well, when you’re dealing with an infinite
number of problems, that seems like an unanswerable

75
00:04:27,390 --> 00:04:31,440
question, but it turns out that a bunch of
these problems—like the traveling salesman

76
00:04:31,440 --> 00:04:36,070
problem and sudoku—are actually technically
the same problem at their core, and this problem

77
00:04:36,070 --> 00:04:40,570
happens to capture the most difficult aspects
of NP; this means that if you come up with

78
00:04:40,570 --> 00:04:45,630
a proof for one of these so-called “NP-complete”
problems, you can use it to solve everything

79
00:04:45,630 --> 00:04:47,410
else in NP.

80
00:04:47,410 --> 00:04:52,900
You could use it to route packages with 100%
efficiency or accelerate our methods for protein-folding…

81
00:04:52,900 --> 00:04:56,230
but you would also break most of our current
financial encryption systems, so you’d probably

82
00:04:56,230 --> 00:04:58,540
have to hide that prize money under your mattress.

83
00:04:58,540 --> 00:05:02,400
So, I was going to tell you that once you
won a million dollars from solving one of

84
00:05:02,400 --> 00:05:05,850
these problems that you should invest in a
quality kitchen knife, but it turns out you

85
00:05:05,850 --> 00:05:07,870
don’t need a million for that.

86
00:05:07,870 --> 00:05:12,320
My least favorite part of cooking used to
be the prep: dicing potatoes, mincing garlic,

87
00:05:12,320 --> 00:05:14,490
trimming meat—you know, the knife-y bits.

88
00:05:14,490 --> 00:05:19,250
But then I got this: the Chef’s Knife from
our sponsor, Made In.

89
00:05:19,250 --> 00:05:22,570
I sliced some cantaloupe, tried to catch my
phone with the hand with the knife, found

90
00:05:22,570 --> 00:05:26,540
out why the box includes a bandaid, sliced
some sweet potato, and man was that the most

91
00:05:26,540 --> 00:05:31,450
pleasurable sweet-potato slicing experience
I’ve ever had—it just cuts like butter.

92
00:05:31,450 --> 00:05:36,280
That’s because Made In sources the finest
materials and partners with renowned craftsmen

93
00:05:36,280 --> 00:05:40,160
to make these kitchen tools and bring them
to you, without the markup.

94
00:05:40,160 --> 00:05:44,610
So, rather than buying a $20 knife that you’re
going to replace every year, invest in one

95
00:05:44,610 --> 00:05:48,830
that’s made for life, and backed by a lifetime
guarantee—it’ll also make your cooking

96
00:05:48,830 --> 00:05:51,160
more fun, fast, and good.

97
00:05:51,160 --> 00:05:55,480
Same goes for pots, pans, bakeware, plates,
and everything else Made In sells—it’s

98
00:05:55,480 --> 00:06:00,210
all high quality, durable, and legitimately
used by professionals in world famous restaurants

99
00:06:00,210 --> 00:06:02,280
like Alinea and Le Bernardin.

100
00:06:02,280 --> 00:06:08,620
Now’s the best time to invest in your kitchen,
as Made In is offering HAI viewers 15% off,

101
00:06:08,620 --> 00:06:13,990
the best discount available anywhere, by going
to MadeIn.com/HALF and using the promo code

102
00:06:13,990 --> 00:06:14,009
“HALF.”