Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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