News for hackers. Stuff that matters.
Re:What if P = NP? by presidentender on Friday April 01, 2011 @01:21PM (#2397105)
The fact that you don't understand why it's dear to so many makes me completely sure that you don't understand the implications. I say that with respect and joviality.

Much of what we do - particularly much of our security - is based on the idea that P != NP, and that those "really hard" problems actually are really hard. For instance, cryptography is based on the fact that prime factorization is NP-hard, so if you use big primes it takes a long time to crack our encrypted information. If P = NP, and someone solves any NP-complete problem, all the NP-complete problems crumble and our security is a thing of the past.

There're good things to come of a constructive P = NP proof, too. We'd have perfect network routing, for one thing. Shipping would be much more efficient. And that damn salesman would finally know that he's getting from New York to San Fransisco and back by way of hundreds of other cities as quickly as possible.

Re:What if P = NP? by dcosson on Friday April 01, 2011 @01:52PM (#2397222)
Factorization is NOT NP-hard. There has never been a proof that guarantees I can't wake up tomorrow and factor any public key on the internet in polynomial time. It just so happens that nobody has figured out how to do it in the history of number theory (or to prove that it's impossible).

Shor's Algorithm factors primes. If prime factorization were NP-hard, that would imply BQP=NP (BQP is Bounded-error Quantum Polynomial time), or at least that BQP contains a subset of NP. Scott Aaronson, who has been linked to here a few times, is firmly convinced that is not true. And the implications of it are nearly as huge as the implications of P=NP! (with the small drawback that we can't actually build quantum computers yet :)

Re:What if P = NP? by presidentender on Friday April 01, 2011 @02:07PM (#2397296)
Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that."

"Hello World" is NP. It's just not useful to talk about that fact.

Re:What if P = NP? by dcosson on Friday April 01, 2011 @02:35PM (#2397432)
"Hello World" isn't a decision problem, but I see your point. However NP-Complete (and by extension NP-Hard) and P are distinct classes of problems, http://en.wikipedia.org/wiki/NP-complete so my statement that factorization is not an NP-Hard problem is true (unless, of course, P=NP).

Either way, my point was that there are systems (i.e. quantum computers) that can factor numbers efficiently, but it is still widely believed that true NP-Complete and NP-Hard problems cannot be solved efficiently even with such systems.

Re:What if P = NP? by bdhe on Friday April 01, 2011 @06:03PM (#2398278)
> Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that."

I'll reiterate. It is unknown if factorization is currently NP-hard. UKNOWN. It is most likely NOT NP-hard otherwise there would be huge implications in Complexity Theory.

It suffices for crypto for problems to be hard on an average. Factoring a random product of two large primes is hard. Factoring is probably not NP hard because no one knows if a factoring algorithm will help solve SAT.

Re:What if P = NP? by presidentender on Friday April 01, 2011 @06:33PM (#2398386)
NP is a superset of P.
Re:What if P = NP? by bdhe on Friday April 01, 2011 @10:27PM (#2398914)
I think I was mistaken in understanding what you said. Yes, factoring is in NP, but it is not known to be NP-hard. Being in NP doesn't automatically imply its usefulness in Crypto (because, as you say, P is a subset of NP). Neither does the NP-hardness of a problem automatically imply its usefulness. Crypto seems to need these weird problems that are not always NP-hard, yet, in some sense, harder than NP-hard problems. You can think of it as: crypto => P != NP, but not vice-versa.
Re:What if P = NP? by masterzora on Friday April 01, 2011 @02:45PM (#2397474)
Alright, I've been slightly unsure with each of your replies in this thread, but this one finally convinces me that you're just good at this "April Fools" thing.
Re:What if P = NP? by NY_USA_Hacker on Friday April 01, 2011 @03:46PM (#2397723)
"Shor's Algorithm factors primes."

Amazing!

Re:What if P = NP? by dcosson on Friday April 01, 2011 @04:19PM (#2397844)
Haha good catch. Should read "factors numbers into primes".
Re:What if P = NP? by bdhe on Friday April 01, 2011 @06:05PM (#2398282)
> If P = NP, and someone solves any NP-complete problem, all the NP-complete problems crumble and our security is a thing of the past.

Security can still be achieved. But it will require exponential time for an honest participant (a much lesser exponent than an adversary, but still exponential time). See: http://en.wikipedia.org/wiki/Merkle%27s_Puzzles It doesn't require P!=NP.