A problem in the NP complexity class can be verified in polynomial time. That is, given a possible answer for a problem in NP, you can come up with an algorithm that will tell you whether the answer is right or wrong in O(nk) steps. See NP-Complete for an easy example problem. It is not known at this time whether or not NP is the same as the P complexity class.