Question: What is an NP-complete problem? Why is it such an important topic in computer science?

Answer: 
I have heard an explanation, that is:"
NP-Completeness is probably one of the more enigmatic ideas in the study of algorithms. "NP" stands for "nondeterministic polynomial time," and is the name for what is called a complexity class to which problems can belong. The important thing about the **NP** complexity class is that problems within that class can be **verified** by a polynomial time algorithm.
As an example, consider the problem of counting stuff. Suppose there are a bunch of apples on a table. The problem is "How many apples are there?" You are provided with a possible answer, 8. You can verify this answer in polynomial time by using the algorithm of, duh, counting the apples. Counting the apples happens in O(n) (that's Big-oh notation) time, because it takes one step to count each apple. For n apples, you need n steps. This problem is in the NP complexity class.

A problem is classified as **NP-complete** if it can be shown that it is both **NP-Hard** and **verifiable** in polynomial time. Without going too deeply into the discussion of NP-Hard, suffice it to say that there are certain problems to which polynomial time solutions have not been found. That is, it takes something like n! (n factorial) steps to solve them. However, if you're given a solution to an NP-Complete problem, you can verify it in polynomial time.

A classic example of an NP-Complete problem is The Traveling Salesman Problem."

The author: ApoxyButt
From: <http://www.everything2.com/title/NP-complete>
NP Problem :-
-------------

1. NP problem are such problem that can be solved in non-deterministic polynomial time.
2. Non deterministic algorithm operate in two stage.
3. Non deterministic guessing stage && Non deterministic verification stage.

### Type of Np Problem

1. NP complete
2. NP Hard

**NP Complete problem :-**

1 Decision Problem A is called NP complete if it has following two properties:-

1. It belong to class NP.
2. Every other problem in NP can be transformed to P in polynomial time.

Some Ex :-

* Knapsack problem
* sub set sum problem
* Vertex covering problem