3 ms·
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 tim
by 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 agoFactorization 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 agoAlright, 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 agoNP is a superset of P.
- bdhe 16y agoI 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 agoHaha good catch. Should read "factors numbers into primes".