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!
Next → ← PreviousMy book "Choose Your First Product" is available now.
It gives you 4 easy steps to find and validate a humble product idea.
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.