## ← 10-46 Border Between NP-Complete And P

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

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

1. Now, before the end of this unit, two words of caution.
2. The first one is that the border between NP completeness and polynomial time
3. can sometimes be very thin.
4. I already mentioned to you that for example 3-SAT,
5. so where you just have three variables in each clause is NP complete
6. but 2-SAT where you just have two variables is solvable in polynomial time
7. and there are many other cases like that
8. but of course this is good news
9. because if your problem turns out to be just as hard to solve as 2-SAT
10. you actually have a polynomial time algorithm for it
11. although it might initially have seemed a bit harder
12. or sometimes even if your original problem possibly is as hard as 3-SAT
13. maybe you can look at a slightly different problem that becomes polynomial time solvable.
14. Because oftentimes there are many different ways to frame
15. the practical problem that you're trying to solve
16. so sometimes you're lucky there.
17. The second thing is an actual word of caution.
18. Because this border here can sometimes be so fragile.
19. It's very important to be precised in your NP-completeness proof.
20. Because sometimes making just a little mistake in an NP-completeness proof
21. can invalidate this whole proof and of course we don't want that.
22. Now, it's time once more to congratulate you.
23. You now know what NP completeness means and how you control NP completeness.
24. And actually not many people can do that.
25. Very few people know precisely what NP completeness means
26. and also they're not capable of showing NP completeness.
27. In the next unit, we're going to take you even one step further.
28. We're going to show you countermeasures against NP completeness.
29. Because even most people that understand what NP completeness means
30. and that can also show NP completeness actually tend to give up
31. once they've shown their problem to be NP complete.
32. But that's actually not necessary because there are many many techniques
33. that she can use to attack even NP complete problems.
34. What should you do when you want to solve the problem and show that is NP complete?
35. Should you carefully check your proof?
36. Should you have somebody else carefully check your proof?
37. Should you give up?
38. Should you maybe try to think about ways of modifying your problem
39. so that it could not be NP-complete or
40. should you try to use the techniques that you're about to learn in the next units of this course.