Posted by: atri | December 5, 2011


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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: