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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Categories

%d bloggers like this: