4 ms·
"P problems are in fact contained within the set of NP problems i.e. non-polynomial time solutions exist for P problems. However, all problems in NP may or may
by loudandclear 14y ago
"P problems are in fact contained within the set of NP problems i.e. non-polynomial time solutions exist for P problems. However, all problems in NP may or may not be in P."
Yes, P is in contained in NP. However, the reason is wrong. It is contained in NP because any problem in P is verifiable in polytime (i.e. by actually solving it).
- dshipper 14y agoI edited that part out to be safe. But I'm curious. I was trying to explain why P problems were in NP and my off the top of my head reasoning was that deterministic non-polynomial time solutions exist for P problems as well as deterministic polynomial time ones. If that's not why P is contained in NP, what's the real reason?
- loudandclear 14y agoSince a problem in P is can be solved in polynomial time, then a solution to it can be verified in polynomial time. If it can be verified in polynomial time, then it is in NP. It's this simple. However, it has nothing to do with "non-polynomial" time solutions, as you originally stated. NP and non-polynomial doesn't have a correspondence by their definitions.
- dshipper 14y agoGot it. Thanks for the clarification.