Re:What if P = NP?
by presidentender on Friday April 01, 2011 @02:07PM
(#2397296)
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.
"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 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.
> 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.
Re:What if P = NP?
by presidentender on Friday April 01, 2011 @06:33PM
(#2398386)
NP is a superset of P.
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.
Re:What if P = NP?
by masterzora on Friday April 01, 2011 @02:45PM
(#2397474)
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.
Re:What if P = NP?
by NY_USA_Hacker on Friday April 01, 2011 @03:46PM
(#2397723)
"Shor's Algorithm factors primes."
Amazing!
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 :)