Name: この問題は暗号を破る可能性がある (This Problem Could Break Cryptography)
Uploaded: 2021-01-14T10:28:53.000Z
Duration: 8 min 8 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

動名詞

Thanks to Brilliant for supporting this episode of SciShow.

命令形

Go to Brilliant.org/SciShow if you're interested in investing in your STEM skills this year.

Think about the last time you checked your credit card balance or how much money you had in the bank.

You probably had to put in your password, which -- if you picked a good one! --

ensures that only you and your bank know how to access your bank accounts.

But what if, no matter how strong your password, a hacker could crack it just as easily as you can type it in?

In fact, what if all sorts of puzzles we thought were hard turned out to be easy?

Mathematicians call this problem P vs. NP, and despite the technical-sounding name,

it is perhaps the single most important question in computer science today.

P vs. NP is a question about algorithms, or sets of specific instructions computers use to solve problems.

If you've done anything on a computer, you've encountered an algorithm before.

But to understand what P and NP are and why people care so much about them,

you need a little background on how algorithms work.

Solving a given problem is an algorithm's most important job, but, after that,

the thing computer scientists care obsessively about is speed.

And presumably, we don't want to wait a year for them.

Computer scientists measure an algorithm's speed using time complexity,

which estimates the time required to solve a problem based on the size of the input.

A real world example for you: think about grocery shoping.

If you have twenty-five items on your list, at the end of the trip, you ought to have twenty-five things in your cart.

But to check that you've got the right things requires comparing every one of those items to what's on your list.

If you're lucky, every time you pick something out of the cart,

it matches the next item on your shopping list.

Then, you'd need only twenty-five comparisons in total.

But maybe you got a couple of impulse buys in there, maybe you skipped some stuff,

in which case you'd be checking each item against the whole list.

Then you look at the list and you're like is this ice cream? No. Is this pickles? No.

Is this mayonnaise… ehhh, this is not good!

Mathematicians call algorithms like these polynomial-time algorithms, because their

running time can grow like the number of items to some exponential power.

In the case of your grocery cart, we've got twenty-five times twenty-five, or twenty-five-squared, so the power is two.

That tells us that a twenty-five-item shopping list could require up to six hundred twenty-five comparisons,

but a fifty-item list would require twenty-five hundred!

In which case, your algorithm would be much slower.

It would take the computer longer to compare everything.

As bad as that sounds, other algorithms are way worse.

Think back to the password on your bank account.

Currently, the only way we know to figure out a random password is guess-and-check.

So let's imagine you make a really dumb password, like something that's twenty-five characters long,

but only uses the letters “a” and “b.”

Since there are two choices for each character, your total number of possibilities is

two times two times two and so on, which mathematicians might write as two-to-the-twenty-fifth power.

At first glance, that might seem like it has polynomial complexity like grocery shopping, but look a little closer.

In the grocery store, our algorithm had speed n-to-the-two, or the number of things to check raised to the second power.

But guessing and checking a password has speed two-to-the-n, or two raised to however many inputs you have.

That's what computer scientists call exponential-time complexity.

And it might seem like a small difference, but its effect is not small.

If it takes one second to check a grocery item from a list of twenty-five things,

then at worst, you'd be done in about ten minutes.

But if it takes a second to make one password guess for a password that's twenty-five

characters long, you could be guessing for over a year.

That difference is why computer scientists generally consider polynomial algorithms “fast” and exponential ones “slow.”

Mathematicians label the set of all problems that can be solved by a polynomial algorithm P.

And they call the set of all problems whose answers can be checked by a polynomial algorithm NP.

The distinction is a little subtle, but NP consists of all the stuff you might spend

hours slaving over, only to have someone glance at your answer and say, “Yeah, that's right.”

It might take you days to put together a ten-thousand-piece puzzle,

but it will only take a very brief amount of time to know whether you did it right.

A bot might spend hours trying to guess your login using an exponential algorithm,

but when you type in the correct characters, a website knows almost immediately if you're in the clear.

Basically, these problems are ones that are fast to check, but slow to solve.

The big question is, are these two types of problems the same?

If so, that would mean that every problem you can check quickly also has a fast, easy solution.

It might just sound like a bunch of math, but finding out whether this is true is seen

as so important that the Clay Mathematics Institute has offered a million dollars for a correct proof.

And as you might expect with that kind of prize money,

people are using basically every field of modern mathematics to try and provide one.

Unfortunately, simpler math problems than this in the past have taken centuries or even millennia to solve.

So, figuring out if P equals NP could take a while.

And in the end, well, we might realize that P doesn't equal NP.

That some algorithms will always take a long time to run.

In fact, many mathematicians and computer scientists think that's probably the case.

But they're still looking because of the implications here… not just because of the prize money!

If P really does equal NP, we will have found an almost-magical key capable of unlocking virtually any computer science or math problem.

And while that could be great in some cases, it could be disastrous in others.

Like, the most immediate casualty would be the complete collapse of modern encryption.

That's stuff like the entire internet, banking passwords we looked at before...

The fact that they're hard to guess and easy to check is what makes passwords useful,

so if P is equal to NP, that advantage would go out the window.

See, here's the thing: Even if we wake up tomorrow and discover P equals NP, all hope of security might not be lost.

I said before that computer scientists usually think of polynomial algorithms as fast.

And that's reasonable for polynomials like n-squared or n-cubed.

But what if the actual polynomial is n to a millionth power, or the billionth?

Sure, it would be part of P, but it would still be way too slow to be of practical use.

The discovery would still be transformative for math, but, in that case, our lives -- and our money -- might still be safe.

So, for the sake of learning and exploration, let's hope we can figure this out.

Because finding answers and discovering new things is one of the best parts of science and being alive!

Still, when or if we do crack this code… it'd be nice if the results were in our favor, too.

If you want to learn more about problems like these, Brilliant has you covered.