5 ms·

Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 http://arxiv.org/abs/1101.2018 A list of articl

Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 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 http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month or so :)

ot 16y ago
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 :)
- Peaker 16y ago
  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.
  - ot 16y ago
    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.
- socketpuppet 16y ago
  How so? 1) One time pads are provably secure albeit impractical 2) Integer factorization is BQP, but not necessarily NP-complete.
  - ot 16y ago
    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)
    - jbri 16y ago
      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.
    - smallblacksun 16y ago
      One time pads are not useful in many cases, but they have been used: http://en.wikipedia.org/wiki/One-time_pad#Historical_uses http://en.wikipedia.org/wiki/One-time_pad#Historical_uses
- dantheman 16y ago
  I completely disagree - think of all the useful np problems that we'd be able to solve in the large scale.
- amalcon 16y ago
  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.

ot 16y ago

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 :)

Peaker 16y ago
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.
- ot 16y ago
  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.
socketpuppet 16y ago
How so? 1) One time pads are provably secure albeit impractical 2) Integer factorization is BQP, but not necessarily NP-complete.
- ot 16y ago
  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)
  - jbri 16y ago
    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.
  - smallblacksun 16y ago
    One time pads are not useful in many cases, but they have been used: http://en.wikipedia.org/wiki/One-time_pad#Historical_uses http://en.wikipedia.org/wiki/One-time_pad#Historical_uses
dantheman 16y ago
I completely disagree - think of all the useful np problems that we'd be able to solve in the large scale.
amalcon 16y ago
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.