The (Unofficial) ITWorx Technical Architecture Blog

Archive for the ‘Algorithms’ Category

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 🙂

Posted in AFathalla, Algorithms | Leave a Comment »

What is an NP-Complete problem?

Posted by archworx on March 15, 2007

So,  you must have heard this term before. I had heard it before and was really looking forward to know it. Yesterday I learnt it in my algorithms class.  Basically, computer scientists have considered algorithms that execute in polynomial time (n^k) (where n is the size of the problem k is a constant and  ^ denotes power)  better than those solved in exponential time (k^n) (where k is a constant and n is the size of the problem ^ denotes power). This is a bit intuitive because exponential time algorithms have a tremendous growth rate (as the problem size increases, the time needed to solve it increases exponentially). After this quick introduction lets turn back to NP-complete problems. Strictly, NP-complete problems are defined as a class of problems/algorithms which if one can be solved in polynomial time then all others can be solved in polynomial time, and since people have been unable to prove for more than thirty years that even one of these problems can be solved in polynomial time, it is unlikely (to our current knowledge) that they can be solved in polynomial time. In other words (from my understanding) if a problem is NP-complete then we cannot  (to our current knowledge) solve it using an efficient algorithm (one that takes polynomial time).  This is because the problem grows very rapidly with increase in input, and is practically unsolvable for large values of n. An example of an NP-complete problem is the well known traveling salesman problem . For more on the issue of NP-completeness read the wikipedia article.

Posted in AFathalla, Algorithms | 2 Comments »