# Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]

Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how to prove a questions is NP, but instead asking why, we can just do so? If there is more step we need to do, what are missing here?

I am not sure why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem in NP because seem to me that we can also verify a solution of a problem is polynomial time while it is actually linear time, can't we?

Proving that a problem is in NP seem requires one additional step? it is really necessary ?

## marked as duplicate by David Richerby, Evil, Discrete lizard♦, Pål GD, Yuval FilmusJan 24 at 18:43

• Hey! There is no such thing as an NP problem. A problem can be in NP, and a problem can be hard for NP and a problem can be complete for NP. And it can be neither. – Pål GD Jan 23 at 18:56
• @PålGD You are wrong. NP is a class of decision problems. So, there is such a thing as "NP problem". NP-complete and NP-hard are more specific things. Everything inside NP is an NP problem. – nbro Jan 24 at 16:49

The class $$P$$ is a subset of the class $$NP$$, that is, problems that have a (deterministic) polynomial-time solution are also included in the $$NP$$ class, the class of problems which have a non-deterministic polynomial-time solution. In other words, if you can solve a problem in polynomial time deterministically, you can definitely solve it in polynomial time non-deterministically.
Therefore, if you are able to verify (in polynomial time) that a solution or algorithm $$s$$ for problem $$t$$ runs in polynomial time (that is, if you are able to verify that $$t \in P$$), then you automatically show that the problem $$t$$ is also in $$NP$$ (because $$P \subset NP$$).