0
$\begingroup$

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 ?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – Pål GD Jan 23 at 18:56
  • $\begingroup$ @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. $\endgroup$ – nbro Jan 24 at 16:49
0
$\begingroup$

I think that your doubt is legitimate. I assume that you know the difference between deterministic and non-deterministic (e.g. state machines), but maybe this is actually the root of your doubt.

First of all, note that a linear-time algorithm is a polynomial-time algorithm (by definition).

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$).

$\endgroup$
  • $\begingroup$ Yes, i forgot the basic, why "that a linear-time algorithm is a polynomial-time algorithm (by definition)". $\endgroup$ – CCOthers Jan 24 at 16:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.