English subtitles

← 16-07 Poor Bob And Carol

Get Embed Code
1 Language

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

  1. Now here, just because the fact 3 approximation algorithm
  2. for vertex cover doesn't carry over here
  3. doesn't mean doesn't mean there can not be an approximation algorithm
  4. for Clique and Independent Set;
  5. it's just that we can not use this one.
  6. So Bob and Carol still don't have to be unhappy,
  7. but unfortunately, I'm now going to make them very unhappy.
  8. For Clique and Independent set,
  9. there is no constant factor approximation algorithm
  10. unless P equals NP.
  11. That, of course, is a very unpleasant surprise
  12. and it's very surprising,
  13. so where did I get that from?
  14. Well, the proof for this result here
  15. relies on some very, very deep results
  16. of theoretical computer science
  17. which you will only get to know in very advanced
  18. theoretical computer science courses, if ever.
  19. But what I would like to do is just give you an intuitive idea
  20. for why there is no constant factor approximation algorithm
  21. for Clique and Independent Set
  22. unless P equals NP.