[ExI] A breakthrough in computer science?

[Anders Sandberg]

I am sceptical that this breakthrough has any practical effects. It is 
important theoretically, but not in practice. Vide Scott Aaronson:
http://www.scottaaronson.com/blog/?p=2521
>
> In practice, I think, a quasipolynomial-time algorithm is better than 
> an n^50 algorithm, but worse than an n^2 algorithm. Unless the 
> constants are absurd, it’s certainly a lot better in practice than an 
> exponential algorithm.
>
> 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 
> <http://www3.cs.stonybrook.edu/%7Ealgorith/implement/nauty/implement.shtml> 
> 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.
>


-- 
Anders Sandberg
Future of Humanity Institute
Oxford Martin School
Oxford University

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20151112/5093c633/attachment.html>