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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.