4 ms·

We're not multiplying N by P. P and NP are complexity classes. Essentially, a problem is in class P (for polynomial) if an optimal solution can be found in pol

We're not multiplying N by P. P and NP are complexity classes. Essentially, a problem is in class P (for polynomial) if an optimal solution can be found in polynomial time (that is, if the number of steps required to solve the problem is at most a polynomial function of the number of factors to check). So if you have a problem, and you can always solve it in polynomial time, it's in P. A problem is in class NP (for nondeterministic polynomial) if the optimality of any solution can be checked in polynomial time. So if you have what you think is a solution, and you can always verify that in polynomial time, the problem is in NP. We know trivially that NP is a superset of P: any P problem has to be an NP problem, because determining the solution in polynomial time counts as checking that solution in polynomial time. What we're not sure of is whether NP is a proper superset of P: the two could be equivalent, and we could just be overlooking polynomial-time algorithmic solutions to the problems we currently believe to be NP but not P.

tibbon 16y ago
Thanks for the answer. I'm not sure why I was downvoted, because I have looked it up before but just didn't understand. Not everyone gets everything the first time or went to school for CS so I highly appreciate you taking the time to explain. I'm curious also why this problem is so near and dear to many people. I'm not sure I understand the implications.
- presidentender 16y ago
  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]

tibbon 16y ago

Thanks for the answer. I'm not sure why I was downvoted, because I have looked it up before but just didn't understand. Not everyone gets everything the first time or went to school for CS so I highly appreciate you taking the time to explain. I'm curious also why this problem is so near and dear to many people. I'm not sure I understand the implications.

presidentender 16y ago
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]