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.