How important is the problem of whether or not P=NP?

'The question of whether P=NP has been occupying researchers since these two sets were first defined, having become the greatest unsolved problem in computer science...'
from Alan Turing: Life and Legacy of a Great Thinker

How important is the problem of whether or not P=NP?
'Does P = NP? This is undoubtedly the most profound question in computer science...'
from: Tutorial: Does P = NP?

How important is the problem of whether or not P=NP?

'The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field...'
from Wikipedia Article on 'P=NP' problem

How important is the problem of whether or not P=NP?

[If you can show that P=NP, then] 'most cryptographic algorithms are basically useless'
from comment by Charles on November 15, 2008 06:13 PM

How important is the problem of whether or not P=NP?

'The Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.'
from Wikipedia Article on 'P=NP' problem

OMFG! They offered what!?

'The Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.'
from Wikipedia Article on 'P=NP' problem

I thought that was what you said.

One MILLION dollars!

Problems sure can't get any more profound than that!

one MILLION dollars!

 

My book "Choose Your First Product" is available now.

It gives you 4 easy steps to find and validate a humble product idea.

Learn more.

jervis on November 21, 2008 07:26 sez:

Dude!
You're missing a great opportunity.

Post this problem on mechanical turk:
------
Wanted: Proof that P=NP.
I will pay: $999,000
------
(That's a profit of $1000 in your pocket, just for typing a couple dozen words!)


nobody on November 21, 2008 09:59 sez:

i really just wanted to comment because the spam-filter word was "meatbag". guess that backfired.


Alexey Romanov on November 22, 2008 01:52 sez:

Of course you probably know it, but "[If you can show that P=NP, then] 'most cryptographic algorithms are basically useless'" is wrong.


lb on November 26, 2008 05:32 sez:

It reminds me of this quote from Sneakers:

"There isn't a government on this planet that wouldn't kill us all for that thing."


Scott on November 27, 2008 16:43 sez:

Coincidences freak me out: you post this random thought, and the same week P=NP is the subject of the evening for the Mathematical Algorithms module at uni.

Unfortunately it is not as simple as setting N=1. Bummer. I might actually have to learn something.


lb on November 27, 2008 20:01 sez:

>Unfortunately it is not as simple as setting N=1

or P=0. ;-)

I keep thinking about P=NP at inopportune moments, and wonder why there isn't some case P!=NP can be proved by having a really small problem domain where it can be completed shown that every combination must be considered before a solution is found.


Martin m on May 23, 2010 05:58 sez:

very interested in how you predict the spam word. P is a pisa fish and np is the name of a fish by any other name. Pisa fish are fish just the same.


(By the way, I read every comment and often respond.)

Your comment, please?

Your Name
Your Url (optional)
Note: I may edit, reuse or delete your comment. Don't be mean.