Re: Questions related to NP-complete problem

Some problems are tougher to solve than others, even with the aid of a computer. The idea of NP completeness gives one way of measuring just how difficult a problem is. Because this idea is fairly complex and central to much of the work in analysis of algorithms today, my answer is somewhat long. Here's some links to get you started if you would rather try the web first.

• 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.