Wouldn't that mean that N == 1 and that P == P?
Wouldn't that mean that N == 1 and that P == P?
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.
I'm curious also why this problem is so near and dear to many people. I'm not sure I understand the implications.
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.
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 :)
"Hello World" is NP. It's just not useful to talk about that fact.
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.
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.
Amazing!
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.
Edit: It was at -1