NP-Completeness - Intro to Algorithms Udacity English English (auto-generated)

NP-Completeness - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 8.9K views 30 likes 9 dislikes 23 Feb 2015

Udacity 651K subscribers United States YouTube↗

Click to Play Video

So, now we're in a good position to finally define this notion

so now we're in a good position to finally define this notion of NP completeness that I mentioned in the

of NP-completeness that I mentioned in the beginning of the unit.

beginning of the unit we can say some problem X is np-complete if it satisfies

We can say some problem X is NP-complete if it satisfies two properties.

two properties first it has to be

First, it has to be NP-hard, meaning that nothing

np-hard meaning that nothing in the set NP is

in NP is harder then X. Which is to say that if you could

harder than X which is to say that if

solve X in polynomial time, you could use it to solve everything in NP in polynomial time.

you could solve X in polynomial time you could use it to solve everything in NP

And the second important property is that X

in polynomial time and the second important property is that X itself is

itself is in NP. So its in the set and its as hard as anything in the set.

in NP so it's in the set and it's as

So, it is in fact the hardest in this set.

hard as anything in the set so it is in fact the hardest in the set and though

And though it may seem a little weird to satisfy

it may seem a little weird to satisfy

both of these at the same time, there are actually tons of problems known to be NP-complete.

both of these at the same time there's actually tons of problems known to be

Very often when you go to solve some, to develop some kind of algorithm to solve

np-complete very often when you go to solve some to develop some kind of

a problem and there just doesn't feel like there is anyway to get a foothold

algorithm for solving a problem and it just doesn't feel like there's any way

on it, uh, its a good idea to check: is NP-hard and is it in NP?

to get a foothold on it it's a good idea to check is it np-hard and is it n NP if

If so, its NP-complete. And, uh, at this point now, tons of problems are known to be NP-complete.

so it's np-complete and at this point now tons of problems are known to be

There is lists, there are online websites that list lots of problems.

np-complete there's there's lists there's online websites that list lots

There's wonderfully written books that layout problem after problem after problem.

of problems there's there's wonderfully written books that that layout problem

And sometimes they are really natural extensions of each other and

after problem after problem and sometimes they're really natural extensions of each other and sometimes

sometimes its really quite interesting to see how they are connected to each other.

it's really quite interesting to see how they're connected to each other saying

Saying that some problem is NP-complete tells us an awful lot about that problem.

that some problem is np-complete tells us an awful lot about that problem so

So, let's imagine there is some problem called graph partitioning - which is a real problem.

let's imagine that there's some problem called graph partitioning which is a

And it is related to social networks.

real problem and it is related to social

But, I'm not going to tell you what it is, but I will tell you that its NP-complete.

networks but I'm not going to tell you what it is but I will tell you that it's

Even if you don't know what it is, there are some things that you do know by the virtue of the fact

np-complete now even though you don't know what it is there are some things that you do know by virtue of the fact

that is is NP-complete, assuming that you believe me, you'd know the following:

that it that it's np-complete assuming you believe me you'd know the following

which of these, check all that apply, which of these do you know?

thing so which of these check all that apply which ones do you know if I tell

if I tell you that graph-partitioning is NP-complete does that mean its

you the Kraft partitioning Zen p-complete

NP-hard and therefore a polynomial time solution for that problem

does that mean it's np-hard and therefore that a polynomial time solution for that problem solves

solves everything in NP. Do we know that the problem clique can be reduced to it?

everything in NP do we know that the problem clique can be reduced to it

Given what we've said so far about what we've said so far about clique. Do we know that graph partitioning is in NP, and therefore an exponential time solution would exist?

given what we've said so far in this unit about clique do we know that graph partitioning is in NP and therefore that an exponential time solution would exist

Do we know that it can be reduced to SAT, based on the things I've told you about SAT in this unit?

do we also know or do we know that it can be reduced to Sat based on the things I've told you about sat in this

Check all that apply.

unit so check all that apply

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 201564% match

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

Behind the Scenes of RWBY Cosplay! | Rooster Teeth
Rooster Teeth
863.9K views 13.7K likes 229 dislikes 08 Aug 201360% match

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

Comment construire un poulailler 2. Pondoir, Aérations, Litière, Astuces
Papy Nounn
851K views 3.2K likes 576 dislikes 03 Mar 201560% match

共軍地下黨寫反政府標語，國軍長官為戴罪立功直接舉報，100鞭子直打得皮開肉綻
 77 dramaclips
2.6M views 23.4K likes -1 dislikes 03 Sep 201959% match

Baby Dancing The Samba In Brazil
The Young Turks
2.5M views 3.1K likes 381 dislikes 17 Jun 201059% match

Batman Parody: The Dark Knight is Confused. Key of Awesome #8.
The Key of Awesome
16.8M views 72.8K likes 2.8K dislikes 07 Dec 200959% match

utilise le dentifrice avec le coca, après une seule nuit tu seras émerveillé
ROSEMOONY BIEN ETRE
964.6K views 0 likes -1 dislikes 08 Sep 201959% 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 201659% match

Lets Modify it! - 2017 Yamaha FZ-S FI V2 Hurricane Grey [Part 1]
Phantom Rides
368.7K views 1.6K likes 232 dislikes 27 Aug 201758% match

Me Before You Official Trailer #1 (2016) - Emilia Clarke, Sam Claflin Movie HD
Rotten Tomatoes Trailers
28.9M views 195.2K likes 3.2K dislikes 03 Feb 201658% match

Cardboard Cinema: PAN
Paint
2.1M views 100.6K likes 390 dislikes 06 Oct 201558% match

Beyonce Falling on Stage
The Young Turks
1.2M views 809 likes 667 dislikes 26 Jul 200758% match

Beast Morphers - X-Bikes and Beast-X Cannon | End of the Road | Power Rangers Official
Power Rangers Official
2.4M views 12.6K likes -1 dislikes 16 Mar 201958% match

ep245 unit13 15 l optional reading
Udacity
2.5K views 3 likes 0 dislikes 18 Oct 201254% match

Udacity EP245 unit3 Optional Reading and Homework
Udacity
1.1K views 5 likes 0 dislikes 23 Feb 201548% match

Course Introduction
Udacity
3.6K views 9 likes 0 dislikes 06 Jun 201631% match

Settings Privacy About Contact Donate