P != NP?

Part of the culture of mathematics is to create a list of important mathematics problems and offer a reward for solving them. The Clay Mathematics Institute is currently offer $1,000,000 to anyone who can solve one of seven problems. Grigori Perelman famously solved one of the problems: the Poincaré Conjecture (he also famously declined the million dollars).

A second paper has been submitted; this time, a proposed solution to the “P vs. NP” problem. If true, Vinay Deolalikar will be awarded $1,000,000.

This will not be sorted out for several months (at least), but people generally seem to agree that he has a chance (i.e. he is not a crank). Still, there is quite a bit of skepticism. Several experts have concerns about aspects of the proof, although they are not certain that any actual errors exist. Plus, Scott Aaronson has wagered $200,000 of his own money that an error will be found in the proof.

Even if Deolalikar has a correct proof, there would still be $5 million left (five questions at $1 million per question) in prize money. You should probably start working now.

Advertisements

Tags:

3 Responses to “P != NP?”

  1. Todd Trimble Says:

    For people who are really intent on becoming a millionaire, this has to be about the hardest way to go about it!

    • bretbenesh Says:

      Sure, slow and steady investment is much easier; but solving a really hard math problem is a much more fulfilling way of earning a million dollars!

      At least, I am guessing this is true. I have not yet solved a math problem for a million dollars yet. Nor have I become a millionaire. Perhaps I do not have much authority in this conversation…
      Bret

  2. 2010 in review « Solvable by Radicals Says:

    […] The busiest day of the year was August 10th with 55 views. The most popular post that day was P != NP?. […]

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


%d bloggers like this: