News for hackers. Stuff that matters.
Re:What if P = NP? by presidentender on Friday April 01, 2011 @06:33PM (#2398386)
NP is a superset of P.
Re:What if P = NP? by bdhe on Friday April 01, 2011 @10:27PM (#2398914)
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.