English subtitles

← 09-09 Using Clique To Set Variables

Get Embed Code
1 Language

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

  1. There's 2 cases here; so let's say the graph does have a clique the size of m,
  2. then what will happen is the following.
  3. So it contains exactly 1 vertex
  4. that corresponds to a variable in that clause,
  5. and what we also know is
  6. because we constructed the graph this way,
  7. that we can not have 2 vertices connected here in this graph
  8. where there's a conflict, so what we can not have in this graph, for example
  9. is 1 vertex that represent not x2
  10. and another vertex that represents x2,
  11. because we avoided this in the construction
  12. but this directly shows us how we can
  13. satisfy this Boolean formula here,
  14. so if we have a not x2 here, we just set it to 0
  15. so we could just set this one to false,
  16. so that not x2 becomes true,
  17. then this clause here is satisfied
  18. and also this one over here would be satisfied.
  19. And x1--that's a separate variable,
  20. so we can set it as we want,
  21. and we could set this one to false.
  22. So we have x2
  23. and we can set that to false so not x2 becomes true.
  24. So that becomes true,
  25. that one becomes true,
  26. that one here is false.
  27. Over here, we have not x2 as well,
  28. so there's no conflict here.
  29. x1--we haven't yet talked about x1,
  30. but can just do the same thing; we can set x1 to false,
  31. so the whole thing not x1 becomes true.
  32. We have set it to false,
  33. and we haven't even looked at x3,
  34. but all of the clauses are already satisfied,
  35. and that's actually the cool thing to notice here.
  36. x3 is also not contained in the clique,
  37. so the vertices in the clique tell you
  38. how to set the variables
  39. so that the Boolean formula can be satisfied.
  40. So what if this graph here does not have a clique of size m?
  41. Well in this case, it means that
  42. we have 1 clause group
  43. which is not contained in the clique
  44. and if we have 1 clause group that is not contained in the clique,
  45. this means that there's no vertex
  46. in the clause group
  47. that has connections to all of the other vertices in the smaller clique
  48. that we're looking for,
  49. and that means, due to the way we constructed the graph,
  50. that every vertex
  51. has a conflict with
  52. another vertex in the clique
  53. so if there's no large clique,
  54. this means that every assignment
  55. of true and false of the variables will lead to a conflict
  56. such that at least 1 of the clauses
  57. can not be satisfied.
  58. So then the Boolean formula does not have a satisfying assignment.
  59. So now that we have this reduction,
  60. we know that clique is
  61. NP complete,
  62. which of course makes Bob a little unhappy.
  63. So now what about vertex independent set?
  64. Are those problems NP complete
  65. or are we not sure yet?