CSCI 3104
Algorithms
Fall 1995

Class notes

Page 19

Wednesday, October 11, 1995

NP-complete vs NP-hard

A problem is "NP-hard" if all problems in NP can be transformed into it. The difference to being "NP-complete" is that an NP-hard problem itself need not be in NP. In other words, "NP-complete" is defined as "NP-hard and inside NP."

The only example of an NP-hard problem that is not inside NP discussed in class was the "Halting Problem," which is the problem of deciding for a given program and input whether or not that program on that input will run into an infinite loop (execute forever). This is a classical problem that has been known for a long time to be unsolvable by any program. Compared to it, even NP-complete problem are easy: at least they always allow exhaustive search in principle. This kind of stuff gets discussed in more detail in courses on theory of computation, under the heading of "(un)decidability" or "computability."

Reference

The classical reference on this whole NP-completeness business is Garey and Johnson (1979). It introduces the whole theory and has an extensive inventory of problems known to be NP-complete.

It's not only 3-Colorability that is hard

Boolean Satisfiability

The problem is this. Given a Boolean expression, does there exist an assignment of true and false values that makes the whole expression true.

This problem is shown NP-complete by a transformation from 3-colorability. Such a transformation amounts to stating, in the language of Boolean expressions, that a given graph is 3-colorable. Here is how you can do that.

For each node x in the graph use three Boolean variables, x-red, x-blue, and x-green, and put the following clause into your Boolean expression:

( x-red or x-blue or x-green )

This says, in Booleanese, that node x does get a color.

And for each edge, say between x and y, put this group of three clauses into your Boolean expression:

( not x-red or not y-red ) and
( not x-blue or not y-blue ) and
( not x-green or not y-green )

Those clauses say that neighbors don't get the same color. (I got this wrong in class. I left off the first "not" in each of the three clauses. So sorry.)

"and" together all the pieces to get the overall expression E that goes with the given graph G. What matters about the expression E is that it is satisfiable if and only if the graph G was 3-colorable. This shows that if we could solve Boolean Satisfiability quickly we could solve 3-colorability, and hence everything else in NP, quickly. Boolean Satisfiability is NP-complete.

Not discussed in class, but noted here ...

The Boolean expression that come out of thie above construction are of a special form, conjunctions ("and"s) of disjunctions ("or"s) of variables or negated variables. That form is called "3-conjunction-normal-form", or 3-CNF. So even doing satisfiability for 3-CNF expression ("3-CNF-SAT") is NP-complete. This would come in handy if we tried to transform this problem into further problems to show those problems to be NP-complete.

TSP

Cormen et al shows NP-completeness of "Hamiltonian Cycle," which is TSP with all edge weights equal. This was not discussed in class.

Vertex Cover

There is a fairly simple transformation of 3-CNF-SAT into the "vertex cover problem." Again, we didn't do this in class. The definition of "vertex cover" is in Cormen et al. (I don't have the book with me right now so I can't give you the exact page.)

Not a homework assignment:

... but something to exercise your understanding with ...

Is 4-colorability NP-complete?

In the transformation of 3-colorability into 3-CNF-SAT it can happen that two variables like x-red and x-blue both are assigned 'true' when satisfying the expression. What does that mean in terms of the graph coloring?

Previous page || Next page

Last edited (or copied to this place) at 12:31 PM, Thursday, October 5, 1995.

CSCI 3104 Algorithms Fall 1995