Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by isomorphic on Thursday November 12, 2015 @11:21PM
(#10557988)
Well, 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.
> 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