4 ms·

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 jov

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.

dcosson 16y ago
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 :)
- presidentender 16y ago
  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.
  - dcosson 16y ago
    "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 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.
  - masterzora 16y ago
    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.
  - deleted 16y ago
    [deleted]
  - bdhe 16y ago
    > 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.
    - presidentender 16y ago
      NP is a superset of P.
      - bdhe 16y ago
        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.
- NY_USA_Hacker 16y ago
  "Shor's Algorithm factors primes." Amazing!
  - dcosson 16y ago
    Haha good catch. Should read "factors numbers into primes".
bdhe 16y ago
> 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 http://en.wikipedia.org/wiki/Merkle%27s_Puzzles It doesn't require P!=NP.

dcosson 16y ago

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

presidentender 16y ago
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.
- dcosson 16y ago
  "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 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.
- masterzora 16y ago
  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.
- deleted 16y ago
  [deleted]
- bdhe 16y ago
  > 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.
  - presidentender 16y ago
    NP is a superset of P.
    - bdhe 16y ago
      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.
NY_USA_Hacker 16y ago
"Shor's Algorithm factors primes." Amazing!
- dcosson 16y ago
  Haha good catch. Should read "factors numbers into primes".

bdhe 16y ago

> 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 http://en.wikipedia.org/wiki/Merkle%27s_Puzzles It doesn't require P!=NP.