News for hackers. Stuff that matters.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by abetusk on Thursday November 12, 2015 @05:24PM (#10556581)
Fair enough, though I think the problem space is substantially different (though I didn't mention it above). It's much easier to make (random) 3-SAT difficult instances whereas for GI you needed highly structured graphs. Apparently Johnson graphs were one of the classes of graphs that caused people problems in GI.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by wolfgke on Friday November 13, 2015 @10:28AM (#10560310)
There are other NP-complete problems, where really hard instances are a lot more rare.