## ← 07-08 Seed Problem

• 1 Follower
• 23 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=NQvBU_i86j0" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. And this time we only have one correct answer,
2. which is this one up here.
3. So once we know that SAT is NP-complete
4. and we wanted to show that those three problems,
5. vertex cover, independent SET, and clique are NP-complete as well,
6. we would have to show that if we take any input for SAT,
7. then we can transform it into one of
8. those three problems up here and then solve that.
9. Because that shows us that in a way vertex cover or independent SET
10. or clique are at least as hard to solve as SAT.
11. And because SAT is NP-complete,
12. if one of these problems is at least as hard to solve,
13. then that problem must be NP-complete as well.
14. These two down here are the wrong way around
15. because SAT is NP-complete,
16. which means that this is one of the
17. hardest problems that you will find in NP,
18. so just showing that for example,
19. you could take vertex cover and transform it into an input for SAT
20. would only show you that SAT is at least as hard to solve as vertex cover,
21. but that is the wrong way around,
22. because we want to show that vertex cover is at least as hard to solve as SAT,
23. so those two answers down here are not correct.