English subtitles

← 10-46 Border Between NP-Complete And P

Get Embed Code
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.