Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]
-
05-11-2019 - |
Pregunta
This question already has an answer here:
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 ?
No hay solución correcta