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

1. Title:
   10-46 Border Between NP-Complete And P
2. Description:

3. 0 0:00 - 0:03
   Now, before the end of this unit, two words of caution.
4. 2790 0:03 - 0:08
   The first one is that the border between NP completeness and polynomial time
5. 8390 0:08 - 0:11
   can sometimes be very thin.
6. 10660 0:11 - 0:14
   I already mentioned to you that for example 3-SAT,
7. 14200 0:14 - 0:18
   so where you just have three variables in each clause is NP complete
8. 17580 0:18 - 0:24
   but 2-SAT where you just have two variables is solvable in polynomial time
9. 23960 0:24 - 0:26
   and there are many other cases like that
10. 25890 0:26 - 0:28
    but of course this is good news
11. 27510 0:28 - 0:31
    because if your problem turns out to be just as hard to solve as 2-SAT
12. 31250 0:31 - 0:34
    you actually have a polynomial time algorithm for it
13. 34240 0:34 - 0:36
    although it might initially have seemed a bit harder
14. 36310 0:36 - 0:43
    or sometimes even if your original problem possibly is as hard as 3-SAT
15. 42800 0:43 - 0:47
    maybe you can look at a slightly different problem that becomes polynomial time solvable.
16. 47400 0:47 - 0:50
    Because oftentimes there are many different ways to frame
17. 50260 0:50 - 0:53
    the practical problem that you're trying to solve
18. 52750 0:53 - 0:55
    so sometimes you're lucky there.
19. 54570 0:55 - 0:57
    The second thing is an actual word of caution.
20. 57420 0:57 - 1:00
    Because this border here can sometimes be so fragile.
21. 60430 1:00 - 1:05
    It's very important to be precised in your NP-completeness proof.
22. 64840 1:05 - 1:09
    Because sometimes making just a little mistake in an NP-completeness proof
23. 69000 1:09 - 1:12
    can invalidate this whole proof and of course we don't want that.
24. 72390 1:12 - 1:16
    Now, it's time once more to congratulate you.
25. 75780 1:16 - 1:21
    You now know what NP completeness means and how you control NP completeness.
26. 81060 1:21 - 1:23
    And actually not many people can do that.
27. 83340 1:23 - 1:27
    Very few people know precisely what NP completeness means
28. 87010 1:27 - 1:29
    and also they're not capable of showing NP completeness.
29. 89390 1:29 - 1:33
    In the next unit, we're going to take you even one step further.
30. 93340 1:33 - 1:38
    We're going to show you countermeasures against NP completeness.
31. 98110 1:38 - 1:42
    Because even most people that understand what NP completeness means
32. 101600 1:42 - 1:46
    and that can also show NP completeness actually tend to give up
33. 105900 1:46 - 1:48
    once they've shown their problem to be NP complete.
34. 108090 1:48 - 1:52
    But that's actually not necessary because there are many many techniques
35. 112150 1:52 - 1:56
    that she can use to attack even NP complete problems.
36. 115660 1:56 - 2:01
    What should you do when you want to solve the problem and show that is NP complete?
37. 121220 2:01 - 2:04
    Should you carefully check your proof?
38. 123710 2:04 - 2:07
    Should you have somebody else carefully check your proof?
39. 126790 2:07 - 2:09
    Should you give up?
40. 129150 2:09 - 2:13
    Should you maybe try to think about ways of modifying your problem
41. 133360 2:13 - 2:16
    so that it could not be NP-complete or
42. 135900 2:16 -
    should you try to use the techniques that you're about to learn in the next units of this course.