
Title:
Making a SAT graph  Intro to Algorithms

Description:

All right, so to do the last little bit of this proof to show that 3colorability is NP hard,
¶

we're going to show that if we had the ability to solve 3colorability problems in polynomial time,

then we could solve three SAT problems in polynomial time as well,

and so what we need to be able to do to show that is if you walk up to me with any 3CNF formula,

I can quickly turn it into a 3colorability problem, which is going to be a graph

such that that graph is 3 colorable if and only if the original formula

the 3CNF formula that were given is satisfiable.

So CNF here just means conjunctive normal form.

It's just that form that I showed you before where the formula is the n of a bunch of clauses

and each clause is the or of three literals and each literal is either variable or its negation,

not the variable, so you walk up to me with 3CNF problem,

I turn that into a 3colorability problem that can be colored if and only if the formula is satisfiable.

Sounds like an interesting challenge. So let's get to it. What we're going to be doing is building a graph.

We'll start off by creating some nodes with one node for every possible literal in the formula.

So that's the k different variables of let's say this, just to be concrete.

This formula that we come to has k variables and s clauses and we're going to add three more nodes.

We'll call them true, false, and slack. I'm going to connect up the nodes initially as follows.

Each literal will be connected to slack including true and false

and we're going to connect true and false to each other.

What that means because there's a little triangle here and

we're trying see whether or not it's 3colorable.

The only way that this thing could be 3 colorable is if these three are given three different colors.

So just for concreteness, let's say that the color that slack gets is red.

The color that true gets is blue, true blue and the color that false gets is black, black. False won.

All right, so the graph that we have so far has the property that each of these literals is

going to have be colored either true or false, blue or black, if we're going to 3 color the whole graph.

So that's good, that kind of make it seem like they're actually getting truth assignments.

We have to be a little careful though because literal Vâ and literal not Vâ can't both be true

and they can't both be false but that's an easy thing to fix in a graph colorability problem.

We just connect them with an edge.

So we add one edge for each variable connecting the pair of literals

that can't both be true and both be false.

Now what happens is the only way that we can 3 color this is if each variable is given a blue for

either the variable and black for its negation or black for the variable

and blue for the negation and that's like a truth assignment.

A true/false assignment to that variable..

So any possible truth assignment, corresponds to a 3 coloring.

Any possible 3 coloring, corresponds to the truth assignment.

So far we're in really good shape as far as capturing the idea of the physics of a SAT problem.