## Reduce 3-Colorability to SAT - Intro to Algorithms

• 0:00 - 0:08
Since 3 coloring is an NP and SAT is NP complete, meaning that it's NP hard,
• 0:08 - 0:13
it has to be the case that we could use SAT to solve 3 coloring problems,
• 0:13 - 0:16
but it's actually a little bit interesting to see how you might do that.
• 0:16 - 0:23
So let's take a look, here's a simple little graph and one, two, three, four nodes, four edges
• 0:23 - 0:27
and imagine that we want to try to 3-color this graph.
• 0:27 - 0:31
What we're going to do is we're going to create a ??? formula that is satisfiable
• 0:31 - 0:36
if and only if this graph is 3 colorable, so that it's really the same problem,
• 0:36 - 0:40
and the way that we're going to do that is we're going to create a bunch of boolean variables,
• 0:40 - 0:47
12 of them to be exact, corresponding to each of the four nodes--a, b, c, and d,
• 0:47 - 0:50
and for each node, we'll a boolean variable saying whether that node is
• 0:50 - 0:54
red or green or yellow, the three colors.
• 0:54 - 1:01
For example, assigning the variable a red to true, a green to false and a yellow to false
• 1:01 - 1:06
means that we're coloring the a node red, and so once we've assigned true values,
• 1:06 - 1:11
trues and falses to all 12 of these variables that corresponds perhaps to some coloring.
• 1:11 - 1:16
In fact, you have to be a little bit careful here because if we assigned two of these to true,
• 1:16 - 1:20
which is a perfectly reasonable thing to do in a boolean formula, you can't really interpret this
• 1:20 - 1:27
as a coloring except for may be a is orange, but that's not really allowed.
• 1:27 - 1:37
What we have to do now is given these 12 variables, we have to create a formula that is true
• 1:37 - 1:46
if and only if it corresponds to a valid coloring, meaning that both exactly one of each of these
• 1:46 - 1:49
triples the variables are true and there's no collisions--
• 1:49 - 1:55
for example, we can't have a colored red and b colored red because they're connected by an edge.
• 1:55 - 1:58
They will have to be different if they're connected by an edge.
• 1:58 - 2:05
The formula for this can be generated automatically and I'll give you glimpse at it.
• 2:05 - 2:12
Here it is, at least one version of it, and it's a little bit weird and complicated,
• 2:12 - 2:16
but it actually falls into some nice structures.
• 2:16 - 2:25
First there's a bunch of logic to say that it should be the case that say--
• 2:25 - 2:30
the a red, a green, and a yellow variables, one of them should be true.
• 2:30 - 2:37
If they're all false, then it's not telling us what color a should be, and it also has to be case
• 2:37 - 2:41
that no pair of colors can be true for a given node.
• 2:41 - 2:45
It can't be the case that both a red is true and a green is true, so that's bad.
• 2:45 - 2:51
There has to be at least one true and not the case that both a is both red and green
• 2:51 - 2:57
not the case that a is both red and yellow and not the case that both a is green and yellow,
• 2:57 - 3:02
and we do that for all four of the nodes and that tells us that
• 3:02 - 3:07
there's a meaningful color assignment to the nodes.
• 3:07 - 3:10
Then we have some additional clauses that say--
• 3:10 - 3:14
what can't be the case that a is red and b is red at the same time.
• 3:14 - 3:19
It can't be the case that a is green and b is green at the same time and it can't be the case
• 3:19 - 3:21
that a is yellow and b is yellow at the same time.
• 3:21 - 3:25
What is that saying, that saying the color--whatever the color happens to be--
• 3:25 - 3:32
for a it can't match the color of b and that's because they share an edge in the graph.
• 3:32 - 3:38
For each of the edges in the graph, we have three of these statements to rule out
• 3:38 - 3:42
all possible color matches, so there's three of these for one edge, two edge, three edge--
• 3:42 - 3:45
there's four edges in the graph so we have four blocks of these.
• 3:45 - 3:50
In this formula now as a whole has a satisfying assignment, has an assignment that makes
• 3:50 - 3:56
this whole expression true if and only if there's a coloring, a 3 coloring of that graph.
• 3:56 - 4:00
Now, in this case, I generated this formula by carefully looking at the graph
• 4:00 - 4:04
and going back and forth in making the formula, but you can automate this idea
• 4:04 - 4:06
by just generalizing the way that I did this here.
• 4:06 - 4:10
Why don't you think about how to do that and I'll ask you a question
• 4:10 - 4:12
just to make sure that you got the idea.
タイトル：
Reduce 3-Colorability to SAT - Intro to Algorithms
Video Language:
English
Team:
Udacity
プロジェクト：
CS215 - Intro to Algorithms
Duration:
04:13
 Udacity Robot edited 英語(米国) subtitles for Reduce 3-Colorability to SAT - Intro to Algorithms Gundega edited 英語(米国) subtitles for Reduce 3-Colorability to SAT - Intro to Algorithms Amara Bot added a translation

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• Gundega
• Amara Bot