CSCI 3104
Algorithms
Fall 1995

Class notes

Page 18

Monday, October 2, 1995

Following up on Friday's discussion

Does the coloring actually solve the TSP problem?

What the whole circuit-construction-out-of-coloring-NAND-gates argument shows is that any TSP problem can be turned into a 3-coloring problem. Consequently 3-coloring is at least as hard as TSP.

There is no known fast algorithm for doing 3-coloring (and most experts suspect none exists). If we had one then we could also solve TSP fast. But in the absence of a fast algorithm for 3-coloring all we are establishing is a relationship between two problems (TSP and 3-coloring), not a solution for either one.

How does 3-coloring compare to other problems?

Instead of using TSP in the argument we could have used any problem which has the property that (the quality of) a proposed solution can be checked quickly. For example, take the "assignment problem": Given a bipartite graph where edges between people and tasks mean that the given person is able to carry out the given task, find an assignment of people to tasks (with at most one task per person) that gets all tasks done.

(This problem is discussed under the label "maximum bipartite matching" in Cormen et al, section 27.3, pages 600-604. No need to read that part of the book now except maybe to make sure you got the definition of the problem right. For the present discussion this is just another problem of a certain class and we need not even know if any fast algorithms exist for this problem.)

It is easy to check a proposed "assignment" for correctness. That lets us use the very same argument as with TSP to build a "coloring circuit" and thereby show that 3-coloring is at least as hard as the assignment problem. (This does not prove that the assignment problem is hard, nor does it prove that the assignment problem is easy.)

NP

Problems for which proposed solutions can ve verified easily are referred to as NP problems. The "P" stands for "polynomial time", which is the formal definition of "fast". The "N" stands for "nondeterministic", referring (misleadingly) to a notion that these problems could be solved easily if somehow we were able to build computers that can "nondeterministicially guess" good solutions.

This NP class of problem is very large. It is hard to even think of some optimization problem where the quality of a potential solution isn't easy to measure. What is remarkable about 3-coloring is that is contains all the complexities of all those NP problems. The technical term is that it is "complete", or more precisely, "NP-complete".

Again, Cormen et al covers all of this, in Chapter 36, pages 916-963.

Coming up ...

On Wednesday, we'll look at some other problems that are also NP-complete. Remarkably, there is no shortage of such problems.

Previous page || Next page

Last edited (or copied to this place) at 9:52 AM, Wednesday, October 18, 1995.

CSCI 3104 Algorithms Fall 1995