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

cs.stackexchange https://cs.stackexchange.com/questions/103261

문제

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 ?

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top