P vs. NP

Recently out in mathdom a man named Vinay Deolalikar has quietly sent out what he claims is a proof that P ≠ NP to a few individuals who then proceeded to yell the fact about the internet. Now, most people who are reading this blog have no idea really what P or NP means, and neither do I. But, what I do know is that this is one of the big open questions in mathematics, one of the seven Millennium Prize Problems.

The question to be solved is essentially this: Suppose that answers to a question can be verified quickly. Then, can the answers themselves also be computed quickly?

Notice the difference between verifiability and computability.

If I asked you to find a subset of {-1, 3,-98, 36, 5, 4, -7, 10} that summed to 0 it would take you a while. However if I told you here is an answer that proves it: {-1, 3, 5, -7}, you would be able to verify it quickly.

The rest of it is a lot of computer science ideas that are a little much to go on about on a Math Club Blog, but if you are interested in the goings on check Richard Lipton’s blog for lots of info about the status of this new possible proof.

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