News for hackers. Stuff that matters.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by chucknthem on Wednesday January 19, 2011 @06:45PM (#2121805)
Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018

A list of articles published on the P=NP debate is here http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Looks like someone thinks they've solved the problem every month or so :)

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by ot on Wednesday January 19, 2011 @06:54PM (#2121850)
And as always, we'd better hope that the proof is wrong. P=NP would (almost) imply the impossibility of cryptography, but even more seriously a lot of brainpower from the top theoretical computer scientists (whose proofs often begin with "suppose that P != NP...") would have been wasted :)
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by Peaker on Wednesday January 19, 2011 @07:01PM (#2121872)
P=NP does not imply cryptography is impossible at all.

For example, "Quantum encryption" allows you to send data and know whether you're being eavesdropped. Then, once you manage to send it without being eavesdropped, you can use what you sent as a one-time-pad safely.

You could of course regress to distributing one time pads to everyone :-)

Also, if P = NP, there are still NP hard and Exp problems that remain outside the realm of P.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by ot on Wednesday January 19, 2011 @07:36PM (#2121979)
That's why I said "almost" :) AFAIK, cryptography without P != NP is an open question.

BTW, quantum encryption is not encryption as we know it (a purely functional deterministic bijective transformation of the message), as it requires special hardware, optical fibers, etc...

As of EXP etc... I am not aware of any (theoretical) encryption schemes that use problems harder than NP (actually most use circuit complexity, so NP/poly, but it is related). In designing encryption you often want polynomial verifiability (for decryption), and that implies NP membership.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by amalcon on Wednesday January 19, 2011 @09:26PM (#2122319)
The negative effects of ruining public-key cryptography completely pale in comparison to the benefits. The traveling salesman problem alone has so many practical and scientific applications that it would be worthwhile, and that's not even counting subgraph isomorphism or knapsack.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by socketpuppet on Wednesday January 19, 2011 @07:11PM (#2121912)
How so?

1) One time pads are provably secure albeit impractical

2) Integer factorization is BQP, but not necessarily NP-complete.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by ot on Wednesday January 19, 2011 @07:31PM (#2121960)
1) One time pads require a secure channel to transmit the key, which must be the same length of the message. It is not a feasible cryptography scheme, more of a theoretical framework.

2) Integer factorization is trivially in NP (the decision problem "n has a factor < x" has a certificate: the factor)

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by jbri on Wednesday January 19, 2011 @07:41PM (#2121995)
A quantum channel provides protection against eavesdropping for random data, but does not provide security for specific data. A shared quantum channel can be used to easily produce a shared one-time key that only the two parties involved know, which can then be used to encrypt specific data over an unsecured channel.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by smallblacksun on Wednesday January 19, 2011 @08:53PM (#2122216)
One time pads are not useful in many cases, but they have been used:

http://en.wikipedia.org/wiki/One-time_pad#Historical_uses

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by dantheman on Wednesday January 19, 2011 @09:02PM (#2122242)
I completely disagree - think of all the useful np problems that we'd be able to solve in the large scale.