Proving NP complexity

Question

I'm learning how to prove something is NP. In Thomas Cormen's intro to algorithm book, he states something is NP if given a solution to some problem, you can verify it is correct in polynomial time.

Say the problem is 2x + 9 = 55, and let's pretend I don't know how long it takes the find the correct x value, but an algorithm to solve the problem returned the solution 23. Then to show it is NP, do I only need to plug 23 in back in the equation, and see if that took a polynomial time and gave me 55? Thanks.

Answer 1

Yes; if you can check the correctness of every correct and every incorrect answer for every instance of this problem in polynomial time, then the problem is in NP.