
<html>

  <head>

    <meta content="text/html; charset=windows-1252"

      http-equiv="Content-Type">

  </head>

  <body bgcolor="#FFFFFF" text="#000000">

    I am sceptical that this breakthrough has any practical effects. It

    is important theoretically, but not in practice. Vide Scott

    Aaronson:<br>

    <a class="moz-txt-link-freetext" href="http://www.scottaaronson.com/blog/?p=2521">http://www.scottaaronson.com/blog/?p=2521</a><br>

    <blockquote type="cite">

      <p>In practice, I think, a quasipolynomial-time algorithm is

        better than an n<sup>50</sup> algorithm, but worse than an n<sup>2</sup>

        algorithm. Unless the constants are absurd, it’s certainly a lot

        better in practice than an exponential algorithm.</p>

      <p>But then again, <i>in practice</i>, graph isomorphism has

        already been “basically in P” for decades! If you have two large

        graphs for which you <i>actually</i> need to know whether

        they’re isomorphic, just <a

href="http://www3.cs.stonybrook.edu/%7Ealgorith/implement/nauty/implement.shtml"

          rel="nofollow">download NAUTY</a> and run it.</p>

      <p>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.</p>

    </blockquote>

    <br>

    <br>

    <pre class="moz-signature" cols="72">-- 

Anders Sandberg

Future of Humanity Institute

Oxford Martin School

Oxford University</pre>

  </body>

</html>