P=NP? - Intro to Algorithms Udacity English (auto-generated) English

P=NP? - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 1.5K views 11 likes 1 dislikes 23 Feb 2015

Udacity 651K subscribers United States YouTube↗

Click to Play Video

this brings us to a point where we can ask one of the most fundamental questions in theoretical computer

This brings us to a point where we can ask one of the most fundamental questions in theoretical

science and that is does P equal NP and in particular here's what we actually

computer science and that is does P=NP and in particular, here's what we actually know.

know this is true we know that every problem that's in P is in NP and every problem that's in NP is in X that is to

This is true. We know that every problem that's in P is in NP and every problem that is NP is in EXP,

say any problem that you can solve in

that is to say any problem that you can solve in polynomial time,

polynomial time we can certainly solve in non-deterministic polynomial time and

we can certainly solve in non-deterministic polynomial time,

any problem that we can solve a non-deterministic polynomial time we can

and any problem that we can solve in a non-deterministic polynomial time,

also solve in exponential time but here's what we don't know it could be

we can also solve in exponential time, but here's what we don't know.

the case that the class NP is actually equal to the clasp exp that that is to

It could be the case that the class NP is actually equal to the class EXP.

say the set of problems that we can solve a non-deterministic polynomial

That is to say the set of problems that we can solve in a non-deterministic polynomial time

time might be exactly the same as the ones that we can solve in exponential

might be exactly the same as the ones that we can solve in exponential time.

time so there's a sort of outer set and that's distinct from say this inner set

So there's a sort of outer set and that's distinct from say this inner set,

which is the set of problems that are

which is the set of problems that are solvable in polynomial time.

solvable in polynomial time oh there's one other thing that we know we do know

There's one other thing that we know, we do know that there really

that there really is a difference between polynomial and exponential time

is a difference between polynomial and exponential time.

there are some problems that can be solved in exponential time that are

There's some problems that can be solved in exponential time that are definitely not NP.

definitely not in P so we know those two things are different but we don't really

So we know those two things are different, but we don't really know.

know it could be that NP is equal to X it could also be that P is equal to NP

It could be that NP is equal to x. It could also that P is equal to NP.

so the problems that we can solve a non-deterministic polynomial time might

So the problems that we can solve in a non-deterministic polynomial time

be exactly the same as the ones that we

might be exactly the same as the ones that we can solve in polynomial time,

can solve in polynomial time which both would be then different from

which both would be then different from exponential time

exponential time or it could very well be that there are really three different

or could very well be that there are really three different categories here.

categories here that that problems that are in NP don't necessarily require

That problems that are in NP don't necessarily require exponential time,

exponential time but they may not be solvable in polynomial time either we

but they may not be solvable in polynomial time either--we don't know.

don't know so this question of whether or not P equals NP whether we're in this case here is is a pretty heavy question

So this question of whether or not P=NP, whether we're in this case here is a pretty heavy question.

so what happens if P does equal NP well a lot of people say a lot of different things let's turn this into a quiz to

So what happens if P does equal NP. Well, a lot people say a lot of different things.

see what you think so one possibility is

Let's turn this into a quiz to see what you think.

that cryptographic protocols so things for keeping secrets and encrypting data

So one possibility is that cryptographic protocols, so things were keeping secrets in encrypting data

that are based on problems like factoring that are in NP could be

that are based on problems like factoring that are in NP could be cracked.

cracked another is that there's a whole lot of computer science to your tissues

Another is that there's a whole lot of computer science theoreticians

who will suddenly be out of work because they will no longer be having to think about this problem another possible

who will be suddenly out of work because they will no longer be having to think about this problem.

outcome might be that with P equal to NP

Another possible outcome might be that with P equal to NP

that means that computers be smarter than people they'll be able

that means the computers will be smarter than people.

to solve problems fast that people can't

They will be able to solve problems fast that people can't.

so I don't know just tell me which one you think is true

So I don't know, just tell me which one you think is true.

Similar videos:

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Tribute to Monty Oum | Rooster Teeth
Rooster Teeth
2.3M views 161.7K likes 691 dislikes 04 Feb 201554% match

Now United & R3HAB - One Love (Official Music Video) | Reaction

45.8K views 4.4K likes 23 dislikes 13 Dec 202054% match

Me Before You Official International Trailer #1 (2016) - Emilia Clarke, Sam Claflin Movie HD
Rotten Tomatoes Trailers
6.8M views 75.3K likes 0 dislikes 28 Mar 201654% match

What Happens To Your Poop In An Airplane Toilet
Facts Verse
2.9M views 13.2K likes 1.3K dislikes 01 Jan 201753% match

asynchronous three-phase motor current calculation
Daniel Santa Cruz // eléctrica
1.5K views 38 likes 0 dislikes 31 Mar 202053% match

New Kids X-men Rise of the mutants Mystique, Wolverine, Apocalypse, batman superhero real life movie
SuperHeroKids
6.7M views 28.8K likes 3K dislikes 17 Jun 201653% match

CONVERTIMOS NUESTRO BAÑO EN UNA MONTAÑA NAVIDEÑA | LOS POLINESIOS VLOG
LosPolinesios
97.1M views 1.3M likes 0 dislikes 16 Nov 201753% match

One 2 One, No. 20 - Sweet Reality
Prem Rawat Official
18.2K views 884 likes 11 dislikes 17 Nov 202053% match

The Clock Is Ticking...
Unbox Therapy
2.6M views 58.4K likes 2K dislikes 26 Sep 201652% match

RT Shorts - Gratuities are Appreciated
Rooster Teeth
1.4M views 13.5K likes 116 dislikes 17 Jul 200952% match

BANA BU SESİ BULUN ! Mala Ustası Genç Ses Analizi
Emre Yücelen Vocal Coach Istanbul (Online Education)
4M views 47.5K likes -1 dislikes 02 Feb 202052% match

SUNNY FAMILY CULT | “7 Minutes in Heaven” | S1E4 | Crypt TV Monster Universe | Short Film
Crypt TV
2.3M views 33K likes 1.1K dislikes 12 May 201752% match

RARE 💜 Selena Gomez 👾 Girl Coder Music Video Story
Jenstine
3.3M views 43.3K likes -1 dislikes 12 Jan 202052% match

Alimento para fortalecer los músculos de los peces
Don Miguel Betta
16.7K views 726 likes 14 dislikes 24 Mar 201852% match

小六公司新買2張床，村長藉此打招聘廣告，遠方的朋友也可應聘了
 Small six vision
45.1K views 799 likes 34 dislikes 24 Dec 202052% match

HOW2: How to Deal with a Baby Sibling!
Annoying Orange
3.6M views 14.5K likes 1.3K dislikes 29 Jun 201652% match

Does this Middle Eastern dish seem odd? But it's loved in here قورمه جگر جغوربغور ایوان کلبه جنگلی
The Lime Tree
174.8K views 3.7K likes 123 dislikes 11 Nov 202052% match

a mysterious package has arrived
FinnyCardinal
1.2K views 13 likes 1 dislikes 08 Mar 202051% match

SewaTT COVID-19 Release 6 - Up The Frequency - A film by Inspire (Original Film)
A Film by Sudarshan Motilal
3.2K views 180 likes 3 dislikes 29 Apr 202051% match

Apple's USB - C to Headphone Jack

1.2K views 18 likes 1 dislikes 20 Jun 202051% match

Elite Dangerous Musgravite Deep Core Mining
Ricardos Gaming
15.5K views 307 likes 13 dislikes 27 Nov 202051% match

Morning PIGEON TRAP (Good)
Maney Pigeons
12K views 588 likes 10 dislikes 28 Oct 202051% match

PLAYING WITH ORBEEZ! | We Are The Davises
We Are The Davises
607.7K views 5.2K likes 151 dislikes 26 May 201651% match

Lindsay Lohan Lesbian????
The Young Turks
787.9K views 647 likes 244 dislikes 27 May 200851% match

Behind the Scenes: Dick Wave | Rooster Teeth
Rooster Teeth
1.6M views 26.5K likes 223 dislikes 04 Sep 201251% match

苗大姐上街吃全家桶，2个汉堡一只鸡吃不够，再打包一袋回家【苗阿朵美食】
Miao Aduo cuisine
48.3K views 1.1K likes 80 dislikes 06 Dec 202051% match

Homemade incubator. Take care of the resistance.
HECHO EN CASA
894 views 11 likes 0 dislikes 29 Jan 202051% match

Percent word problem example 4 | Decimals | Pre-Algebra | Khan Academy
Khan Academy
654.3K views 574 likes 57 dislikes 31 Aug 201051% match

The key to making your paintings more exciting.
César Córdova
34.7K views 1.6K likes 30 dislikes 24 Oct 202051% match

Settings Privacy About Contact Donate