Posted by: atri | December 5, 2011

## Duh…

I said something really stupid in class: if they handed out licenses to theoreticians, mine would have been revoked today 😮

It is not too hard to see that $\mathsf{P}\subseteq \mathsf{NP}$. (If you do not see it immediately, think about it!) This means that unlike what I wrote on the my last page, there are only two possibilities: either $\mathsf{P}\cap \mathsf{NPC}=\emptyset$ or not. (The latter implies $\mathsf{P}=\mathsf{NP}$.)

I’ll correct my notes before I upload them (tomorrow).

Thanks to Scott for pointing this out.