• The Amara On Demand team is looking for native speakers of German, Japanese, Korean, Italian, Hindi and Dutch to help with special paid projects
Apply here Hide

## ← 09-09 Using Clique To Set Variables

• 1 Follower
• 65 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=Ab0boHVEv2o" data-team="udacity"></div> ``` 1 Language

• English [en]

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?