More on NP-Completness
Posted by archworx on May 9, 2007
There has been a post drought on our blog lately, I decided to write a post to elaborate more about the NP-Complete Problems Post I had posted earlier. The subject is not small so I think it will take a series of post.Let’s first begin by defining a set of problems that are called NP. The set of NP problems is the set of decision problems (i.e. have an answer of either YES or NO) that can be verified by an algorithm that runs in polynomial time (Remember polynomial time is n^k where k is a constant). But what does that mean, it means that if we are given an instance of this problem and a solution of the problem we can verify whether or not this solution is a correct one using an algorithm that runs in polynomial time. But does this mean that this problem itself can be solved in polynomial time, not necessarily. There currently does not exist a polynomial time algorithm for the Traveling Salesman Problem (TSP), but given an instance of TSP and a solution we can easily verify whether this solution is correct or not using an algorithm that runs in polynomial time. But wait, we said that NP problems are decision problems and TSP is an optimization problem. That is not an issue, as any problem can be transformed to a decision problem. In the TSP example we can slightly change the problem statement to be “Is there a path that passes by all cities once and only once having a cost no more than x (where x is a positive integer). Now it is easy to create an algorithm that checks that the solution is correct by verifying that all cities were visited and that the cost is less than the one given in the problem statement, it is easy to prove such an algorithm runs in polynomial time. Now that we have defined the set NP lets present a formal definition of the set of NP-Complete problems; a problem Z belongs to this set if:
1- Z E NP (where E is the set notation for ‘is an element of’)
2- Every problem in the set NP can be polynomialy reduced to Z.
But what does polynomialy reduced mean. Well,this will just have to wait for next time.
N.B. I don’t trust my powers of explanation 100% so be sure to post a comment about anything you want elaborated 🙂