MadSci Network: Computer Science |

Posted By:

Area of science:

ID:

- http://hissa.nist.go v/dads/HTML/npcomplete.html
- http://www.cs.unb.ca/~alopez-o/comp-faq/faq.html
- http://mathworld.wolfram.com/NP- CompleteProblem.html

There are two ideas involved in *NP* completeness,
first the *NP* part, and then the completeness part. The term
*NP* stands for "Non-deterministic Turing machine solvable in
Polynomial time", but that doesn't give a good way of understanding
what this class of problems is. A more intuitive approach is to say
that a problem is in *NP* if an answer to the problem can be
checked in polynomial time.

Let's look at the first example you gave, graph 3- colorability (which of course would be colourability if I wasn't American). You stated the problem formally in your question, another way to state it is that I have a graph and I want to know if it is possible to assign each node a color red, blue, or green, so that no two endpoints of an edge are given the same color. Now suppose you walk up to me and give me a coloring that you claim is a valid coloring. I could check that it was a valid coloring in polynomial time by looking at each edge and verifying that the endpoints received different colors (in fact, this only takes linear time).

For your second problem, suppose you gave me a partition
and claimed that no subset of C is entirely contained in either S1 or S2.
Again I could quickly (in polynomial time) check your claim to see if it
is true. So the problem is in the class *NP* of problems.

Now for the "completeness" part. We say that problem A is polynomially reducible to problem B if the ability to solve problem B in polynomial time allows me to solve A in polynomial time. Here's an example: I know how to add and multiply numbers in polynomial time. Multiplying two n x n matrices requires O(n^3) additions and multiplications, so the problem of multiplying two matrices together is reducible to the problems of addition and multiplication of numbers.

A problem is complete for a class if all other problems in
that class can be reduced to it. This raises the question, is there a
problem which is in *NP* for which it is possible to prove that any
other problem in *NP* can be reduced to it in polynomial time? The
answer is yes. The result known as Cook's Theorem says that the 3-SAT
problem is *NP* complete. Reducibility is transitive, so if A
reduces to B and B reduces to C then A reduces to C as well. Let A be any
problem in *NP*. Then by Cook's Theorem, A reduces to 3-SAT.
Suppose that 3-SAT reduced to 3-colorability. Then A reduces to 3-
colorability as well. So that would mean that 3-colorability is also
complete for the class *NP*, or *NP*-complete for short.

In other words, to show that a problem is *NP*-
complete, all we have to show that any other *NP* complete problem
reduces to it. If we were able to show that 3-SAT reduces to 3-
colorability, then we would know that 3-colorability was *NP*-
complete. If we could then show that set partition reduces to 3-
colorability, then set partition would be *NP*-complete. In this way
computer scientists have been building up the list of known *NP*-
complete problems until there are thousands of them.

Because they are all reducible to each other, if an algorithm was found to solve any one of these problems in polynomial time, all of the other problems would be solvable in polynomial time as well. But so far no one has been able to come up with such an algorithm, and so these problems are considered to be very difficult.

Try the links in the MadSci Library for more information on Computer Science.

MadSci Network, webadmin@www.madsci.org

© 1995-2000. All rights reserved.