> No one has ever found an efficient algorithm for an NP-complete problem, and most computer scientists believe no one ever will.<p>I find these kinds of assertions somewhat misleading. There _are_ "efficient" algorithms for, one could say, "pragmatic variations" of NP-complete problems. Some only work on some subset of cases (perhaps most of the useful ones), or non-deterministic (but you run them enough times and get the right answer), etc.
Ok so the question is, while theoretically this is an important work, is it really worthy having a practical implementation?<p>(I remember something similar happening with "Primality testing is P" but the existing, non-P algorithms were good enough so people wouldn't bother using it except in specific situations)
Is somebody able to explain in more detail what the "Greater metropolitan area" of P space means? I have a CS undergrad degree so I get what polynomial space is, just not sure about the quasi-p-space part.
What happens with this one ?<p>Polynomial Time Algorithm for Graph Isomorphism Testing.
<a href="http://mt2.comtv.ru/" rel="nofollow">http://mt2.comtv.ru/</a><p>Is this a hoax or has some substance ?
Thanks for posting this. In the future, could you please add the algorithm to the title? This feels a couple steps removed from clickbait. No offense intended; it's just a suggestion.