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.

Answer 2

Adding information to @Mehrdad answer:

Note that NP stands for Nondeterministic Polynomial time - it means that by definition - a problem is in NP if and only if it can be solved polynomially by a Non-deterministic Turing Machine.

It is equivalent to saying that in the standard computation model (RAM machine/ deterministic turing machine) - you can verify an answer in polynomial time (like @Mehrdad answered). The proof for the equivalence is described in the wikipedia page for equivalence of definitions

Bonus:
The question of "is everything that is verifiable (polynomially) on turing machine is also solveable polynomially" and the questions "is everything that is solveable on non-deterministic turing machine polynomially also solveable on deterministic turing machine polynomially" are also equivalent.
The answer is yet unknown and the problem is known as the P vs NP problem, which is the most important open question on computer science.

Answer 3

While the problems above cover the last, and perhaps, most identifiable step of NP-ness, there are 3 basic steps to showing that a problem is in NP.

1. Decision Problem: Can you turn your problem into a decision problem? In the case of the equation problem,the decision problem would be "is there an x such that 2x+9=55?" ?

2. Certificate: Can you identify an answer to your decision question? Again, in the case of the equation problem, an answer might be x = 23

3. Verification: Can you verify a certificate in polynomial time. By verifying in polynomial time, you know that the problem is not NP-Hard. Some verification steps might be: is x a number? is X equal to one half of 55-9?

That is how you know that your problem is completely in NP.