0
$\begingroup$

I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:

The MST problem belongs in NP-Class.

(I mean, i think it is correct, but could someone classify that as wrong because he would expect P instead of NP?)

$\endgroup$

1 Answer 1

1
$\begingroup$

The statement is correct for exactly the reason you started with: $\mathsf P$ is a subset of $\mathsf{NP}$ which means that every problem in $\mathsf P$ is also in $\mathsf{NP}$. You can also go through the definitions and find that a deterministic TM running in polynomial time is merely a special kind of nondeterministic TM running in polynomial time and take it from there.

However, while being true, the statement "MST is in $\mathsf{NP}$" holds less value than the statement "MST is in $\mathsf P$" as complexity theory is, at large, concerned with lower bounds. A decent analogy in my opinion would be that the statement $\pi \geq 3$ is stronger than the statement $\pi \geq 0$ eventhough both are true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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