## ← 09-01 Seed Problem

• 1 Follower
• 35 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=Fj7DPNrete8" data-team="udacity"></div> ``` 1 Language

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

1. Now the hardest part is done.
2. We have a problem we know to be NP complete,
3. and that problem SAT.
4. So from now on, showing that other problems are NP complete
5. will get a lot easier,
6. because we don't have to go through this
7. laborous process n coding machines anymore
8. It will just suffice to show that SAT
9. can be reduced the the problem we're looking at.
10. So we can use SAT to show other problems
11. to be NP complete now,
12. and once we have shown these problems to be NP complete,
13. we can use them as well to show
14. again, other problems to be NP complete,
15. so we are basically building this whole tree of NP complete problems
16. using SAT as a c problem
17. and it will just suffice to show these
18. reductions here; we do not have to
19. do the same tedious steps of Boolean formula n coding anymore,
20. because we already know SAT to be NP complete now.
21. So let's take 1 step back now
22. with our next quiz.
23. What happens if you show one NP complete problem
24. to be solvable in polynomial time?
25. And by solvable in polynomial time, of course,
26. I mean on a deterministic RAM.
27. Would that mean that some problems in an NP
28. can be solved in polynomial time?
29. Again, we're talking about a deterministic RAM here.
30. Would it mean that all NP complete problems
31. are solvable in polynomial time?
32. Or would it mean that all problems in NP
33. are solvable in polynomial time?
34. And again, more than 1 of these answers here can be correct,
35. so please check every statement that is correct.