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

Answer: 
What is [NP](https://en.wikipedia.org/wiki/NP_(complexity))?
------------------------------------------------------------

NP is the set of all [decision problems](https://en.wikipedia.org/wiki/Decision_problem) (questions with a yes-or-no answer) for which the 'yes'-answers can be ***verified*** in polynomial time (O(nk) where *n* is the problem size, and *k* is a constant) by a [deterministic Turing machine](http://en.wikipedia.org/wiki/Deterministic_Turing_machine). Polynomial time is sometimes used as the definition of *fast* or *quickly*.

What is [P](https://en.wikipedia.org/wiki/P_(complexity))?
----------------------------------------------------------

P is the set of all decision problems which can be **solved** in *polynomial time* by a *deterministic Turing machine*. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.

What is [NP-Complete](https://en.wikipedia.org/wiki/NP-complete)?
-----------------------------------------------------------------

A problem x that is in NP is also in NP-Complete *if and only if* every other problem in NP can be quickly (ie. in polynomial time) transformed into x.

In other words:

1. x is in NP, and
2. Every problem in NP is [*reducible*](https://en.wikipedia.org/wiki/Reduction_(complexity)) to x

So, what makes *NP-Complete* so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all *NP* problems can be solved quickly.

See also the post [What's "P=NP?", and why is it such a famous question?](https://stackoverflow.com/questions/111307/whats-pnp-and-why-is-it-such-a-famous-question)

What is [NP-Hard](https://en.wikipedia.org/wiki/NP-hard)?
---------------------------------------------------------

NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having `NP` as a prefix. That is the NP in NP-hard does not mean *non-deterministic polynomial time*. Yes, this is confusing, but its usage is entrenched and unlikely to change.
As far as I understand

P is the set of problems which could be solved in polynomial time with a deterministic TM.

NP is the set of problems which requires a non-deterministic TM to be solved in polynomial time.
This means that we can check all different combinations of variables in parallel with each instance taking polynomial time. If the problem is solvable then at least one of those parallel instances of TM would halt with "yes".
This also means that if you could make a correct guess about the variables/solution then you just need to check it's validity in polynomial time.

NP-Hard is the set where problems are harder than NP. This means NP-Hard problem are more difficult than any problem in NP set. These problems are exponential even when using non-determinism of Turing machines. So parallel computation does not helps while solving these problems.

NP-Complete is the intersection set of NP and NP-Hard. According to what I understood,

1. problems in NP-Complete are at least as hard as the hardest problem in the NP set.
2. The class of all NP-Complete problems are equivalent to each other, i.e, a problem in NP-Complete set can be reduced to any other NP-Complete problem. That means if any of the NP-Complete problem would have an efficient solution then all of the NP-Complete problems could be solved with same solution.

If any problem in NP-Complete set is deterministically solvable in polynomial time, then the entire NP-Complete set is deterministically solvable in polynomial time. Also since NP-Complete problems are at least as hard as the hardest problem in the NP set, all problems in the NP set (which are equal or easier than the problems in NP-Complete set) will be bounded above by deterministically polynomial running time, expanding the P set over the NP set, resulting in P=NP.

Please let me know if I made any mistake.