# Confusion related to P and NP problems

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?

-
The definition of NP says nothing about cannot. If you can solve a problem in polynomial time, you can certainly verify (indeed have verified) in polynomial time. –  André Nicolas Mar 21 '13 at 20:42
It isn't known if $P=NP$ or not. claymath.org/millennium/P_vs_NP would be where you could claim a million dollars if you can honestly prove the "cannot" part of your question. –  JB King Mar 21 '13 at 21:21
@Andre. I didn't get what you said. Refering to the wiki article en.wikipedia.org/wiki/P_versus_NP_problem, it says there are problems in NP (such as NP-complete problems) that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time –  user34790 Mar 22 '13 at 0:04
What I was saying was the converse, if easy to compute then easy to verify. Meaning P is subset of NP. –  André Nicolas Mar 22 '13 at 5:05

The class $P$ stands for "problems solvable in polynomial time on a deterministic Turing machine". The class $NP$ stands for "problems solvable in polynomial time on a nondeterministic Turing machine". Since any deterministic Turing machine can also be considered a nondeterministic one, it follows that $P\subseteq NP$.

The characterization of $NP$ as the class of problems verifiable in polynomial time on a deterministic Turing machine, is equivalent to the above definition, but the proof requires a bit of work, and indeed when formulated that way the inclusion is not clear.

-

By definition:

P is the set of decision problems which can be answered by a Turing machine in polynomial time (meaning the running time depends polynomially on the input size).

NP is the set of decision problems which can be answered by a nondeterministic Turing machine in polynomial time.

Since any deterministic Turing machine is also nondeterministic, P is a subset of NP.

-