The terms P, NP, NP-Complete, and NP-Hard are from Complexity theory, which boil down to 4, generalized categories of the answer to the question "how hard is this problem to solve (with a computer)". As listed, they are 'roughly' in order of less to more complex.
The theory uses 2 models of computation, a 'deterministic Turing machine' and a 'non-deterministic Turning machine'. Both models (which I'll call TMs from now on) are based on a minimalist computation machine, which has:
* a fixed set of states (the machine is always in only 1 state),
* an infinitely long 'tape' of symbols (for both input and output),
* a (single position) tape reader/writer,
* a mechanism for moving the tape 1 symbol left or right, and
* a fixed map of current-state-plus-current-input-symbol to 'action'.
The action is first (possibly) overwrite the input symbol with another symbol, then (possibly) move the tape left or right, and finally change to a new state.
At each step, the current state of the machine and the current symbol under the reader are used to look up what action to do next, and then take that action. Given a long enough tape, anything that we can run on a computer, today, can be simulated by a TM; this facility from such a minimal mechanism is why Complexity theory bases analyses on TMs.
The difference between a deterministic TM and a non-deterministic TM is that a deterministic TM has only 1 choice of action for any state-plus-input pair, while a non-deterministic TM can have more than 1.
"Wait a minute," you ask, "how does a non-deterministic TM choose the 'right' action to solve the problem?"
The answer can be either it somehow always chooses the correct one, if one exists, or that it chooses all of them, and the one that solves the problem 'wins'. (The former might be hard to swallow, but the latter might be better explained, perhaps, by saying that each time a non-deterministic TM is presented with more than 1 action, the TM is cloned, and each clone chooses a different action.) . Think of a deterministic TM as doing its steps sequentially, while a non-deterministic TM works in parallel, with a new copy of the TM for each possible path of execution.
From the difference between deterministic and non-deterministic TMs, you might realize that a deterministic TM is simpler than a non-deterministic TM, and that a non-deterministic TM might be able to solve harder problems, or solve them faster, than a deterministic TM. Right? This is also the difference between P and NP. A problem in P (meaning of complexity P) can be solved with a deterministic PM in polynomial time, while a problem in NP can be solved with a non-deterministic TM in polynomial time. Alternatively, if a problem can be solved by a deterministic TM in polynomial time, then the problem is in P. If it can be solved by a non-deterministic TM in polynomial time, then the problem in in NP.
By polynomial time, we mean that an algorithm can be solved in the amount of time determined by a polynomial of some value (e.g. the size). If the amount of time increases faster than a polynomial (e.g. exponentially), then the problem is more complex than P.
Since a non-deterministic TM can *also* solve P problems, P is a subset of NP (i.e. all P problems are also NP, but not vis versa).
Now, NP-Complete problems are a subset of NP, as well, but *not* also P, as far as we know, today. And *this* is why your question is important in computer science (and complexity): *If* we were to discover a polynomial time solution to an NP-Complete (or wider, NP) problem, then *all* NP-Complete problems can be, and the class of NP-Complete problems ceases to exist. To date, there is no proof whether this can (or can't) be done, and so it's an open and important question. Important, because of the possibility that very hard problems *might* have easier solutions than we're currently aware.
(In fact, NP-Complete problems are NP problems which are *also* NP-Hard, so 'solving' NP-Complete will likely affect solving other NP-Hard problems, too.)
