TechnicalArchitectureWorx

The (Unofficial) ITWorx Technical Architecture Blog

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.

2 Responses to “What is an NP-Complete problem?”

  1. khaled said

    please help me with pn problems and examples and algorithmes

  2. khaled said

    np problems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: