0
$\begingroup$

I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is correct of not in polynomial time. Then how come P is subset of NP?

$\endgroup$
9
$\begingroup$

The flaw in your thinking is this statement: "NP problems cannot [be solved in polynomial time]". In other words, you seem to be under the impression that NP is an opposite of P. This is not correct.

Class NP contains all problems whose solutions can be verified or checked in polynomial time---but it places no conditions on how difficult the problem is to solve. That is, the standards for Class NP are easier to meet than for Class P.

Honestly, the Wikipedia page on the topic provides a relatively decent overview of the matter. The example of a problem in NP that they give is the "subset sum problem":

Consider the subset sum problem, an example of a problem that is easy to verify, but whose answer may be difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero" can be quickly verified with three additions. However, there is no known algorithm to find such a subset in polynomial time (there is one, however, in exponential time, which consists of $2^n-1$ tries), and indeed such an algorithm can only exist if P = NP; hence this problem is in NP (quickly checkable) but not necessarily in P (quickly solvable).

If you are given a very large set of integers, finding a non-empty subset that adds up to zero is extremely expensive; but given a single potential solution, verifying that it is a valid solution is quite trivial.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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