Slashdot Mirror
New Work Suggests That P Is Not Equal To NP (arxiv.org)
New submitter cccc828 writes: In a new paper Norbert Blum tackles the P=NP question and finds them to be not equal. While this is exciting news (for theoretical computer scientists at least), remember that there is a long list of findings pointing either way.
Even if P were equal to NP it wouldn't mean the end of encyption based security. Most people forget P and NP are asymptotic complexity classes. No real world problem has ever had an instance whose input complexity tends to infinity.
That's why Bubblesort (a sorry ass sorting algorithm) performs better than Quicksort or some other variant for small inputs. But you'd never guess that for the asymptotic complexity analysis.
or Both. But, we can't tell, if P = 0 and/or N = 1
That is what makes it computationally hard ;)
Agent K: A *person* is smart. People are dumb, stupid, panicky animals, and you know it.
The expected answer means we will have cryptographic security available indefinitely. We may have to keep switching algorithms, but in principle there will always be an algorithm out there that can't be quickly bypassed. Evidence that P = NP (or one is a subset of the other) means all cryptography is doomed to fail.
It only takes one specific example to disprove a general proposition.
They can still prove that P = NP for specific cases, but if this proof holds up, the general case is disproven.
John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'