Very briefly:

Context: Some problems are easy, and known to be easy. Some problems appear to be hard, and yet easy to verify alleged solutions. That seems odd - let's have a closer look.

Example:

Consider being given a network and asked if there's a path that visits every node exactly once and returns to its starting point. (This is the task of asking if a Hamilton Cycle exists). If the network is big enough, deciding if this can be done can be really hard. However, checking if someone has successfully done it is easy.

Motivation for a definition of NP:

A problem for which it is efficient (for which read "polynomial") to check a purported solution is said to be in "NP". Knowing whether a Hamilton cycle exists in a network is one of many, many such problems.

Definition: A problem is in "NP" if there is a polynomial time algorithm to test an alleged solution.

Definition: A problem is in "P" if there is a polynomial time algorithm to solve it.

Lemma: All problems in "P" are also in "NP". Proof left to the interested reader.

(Note: technically we are dealing with Decision Problems - problems where the answer is always Yes or No. For example, I didn't ask you to find a Hamilton Cycle, I only asked if there was one. Sometimes the Decision version can be ramped up into actually finding the solution.)

Note that easy problems (for example, finding a cycle that visits every edge exactly once - an Euler Cycle) is also "NP", but it's not a hard NP problem - it's actually in "P". This point confuses a lot of people. NP does not automatically mean hard - that comes in a minute.

Another example:

Similarly, factoring a large integer can be really hard, but if someone claims to have a factor, checking it is as easy as doing the division.

Comparing problems:

Cleverly, it can be shown that if you can solve the Hamilton Circuit problem efficiently, that can be converted into a way of solving the factoring problem. In some very real sense, the Hamilton Circuit problem is harder than (or equal to) the factoring problem.

Finding:

There are many, many NP problems that have been shown all to be equivalent to each other, all to be easy to check solutions, and yet no algorithm for solving in polynomial time known. Such problems are call NP-Complete (NPC) because an efficient algorithm for any of them will completely solve all the NP problems.

So:

* A problem is said to be in "P" if there is an algorithm that takes instances and produces answers in polynomial time.

* A problem is said to be in "NP" if there is an algorithm that takes only polynomial time to check a purported solution for correctness.

* It is unknown if there are any problems that are in "NP", but not in "P".

That is the P vs NP question, and the Clay Mathematics Institute has offered $10^6 for its resolution. You could do this by showing that there is a polynomial time algorithm for any of the NPC problems, or by showing that no such algorithm exists.

Summary:

* P problems are "easy"

* NPC problems are thought to be hard

* There are lots of NPC problems, and solving any one of them would solve all NP problems.

* Integer factoring (IF) is thought to be outside P, but not as hard as NPC.

* There are problems that are harder than all NPC problems, these are called NP-Hard.

So we think that

P < IF < NPC={ Clique, 3SAT, G3C, Knapsack, Ham, ...} <= NP-Hard

But we don't know if these are, in fact, all different. The submitted link is to a paper that says yes, they are all different.

I hope that helps.