3 ms·
Yeah. But as Scott Aaronson points out, GI has a very different feel to factoring. A randomly chosen number will be hard to factor, but it's actually quite hard
by moyix 11y ago
Yeah. But as Scott Aaronson points out, GI has a very different feel to factoring. A randomly chosen number will be hard to factor, but it's actually quite hard to come up with examples of GI that are hard:
> But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it.
> This contrasts with the case of factoring, for which I’d personally say that it remains much less clear whether it should or shouldn’t be in P.
http://www.scottaaronson.com/blog/?p=2521#comment-889824 http://www.scottaaronson.com/blog/?p=2521#comment-889824
- isomorphic 11y agoWell, we're resting at least a trillion-USD economy on that "much less clear"; probably more. Given that, bad actors are properly incentivized to work on factoring, and we can take comfort that we haven't yet heard any evidence yet of a (quasi-) polynomial solution. That is assuming someone couldn't keep something like that a secret.