English subtitles

← 07-05 Proving NP-Completeness

Get Embed Code
1 Language

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

  1. So let's say now that you have a problem
  2. that you know to be an NP such as vertex cover,
  3. and there's basically two ways that you could show this problem to be NP-complete.
  4. The first one is, you could take another NP-complete problem
  5. and reduce it to your new problem.
  6. A second way would be to use the definition
  7. that we just had of NP-completeness
  8. and show that this problem here can be used
  9. to solve any other problem that is also solvable in NP,
  10. and by showing, I mean proving.
  11. That is the first way, and the other way would be to
  12. just use the definition of NP-completeness that we just looked at,
  13. so what you could also do is you could show,
  14. or in this way you would have to prove mathematically,
  15. that any problem in NP can be reduced to your problem.
  16. And the emphasis here is on any problem,
  17. because otherwise, it wouldn't be NP-complete.
  18. And those are the two possible ways you could show NP-completeness.
  19. I will call this here approach number one
  20. and this one up here approach number two.
  21. Now if you look at those two approaches,
  22. this one here sounds much easier in a way than this one here,
  23. because here we just have one problem where we have to have a reduction,
  24. and here we have to have any problem.
  25. Not even some problems, not even a million problems, but really any problem.
  26. But there's a little problem with the first approach here,
  27. and I hope you can tell me what that is.
  28. So what could be potential issues with approach number one?
  29. Could it be that this only works for some problems in NP?
  30. Could it be that before we can do approach number one,
  31. we must first have had success with approach
  32. number two for at least one problem in NP?
  33. Or could it be that approach number one is not always correct?
  34. So please check all of these statements which you believe are true.