Thanks for the suggestions! We fixed (I hope ) the bug you mentioned. Putting primes into “factoring2″ should always result in unsatisfiable instances now.

You’re right about reducing the size of the multiplier – possibly in a future version. There are some other possible “optimizations” not done yet either. Hopefully, the source code will be ready for release soon.

I now think BL always takes worst case time, so it’s irrelevant to the question of hard instances. Miyazaki’s instances probably have two parameters, number of vertices and degree. Keeping degree fixed, they are hard for McKay, but not Luks, but probably letting degree increase they are hard for Luks. Thus they are legitimate hard instances. And it took 10 years for Tener to modify the algorithm to solve them quickly.

So there has been only one hard instance, but it wasn’t quickly resolved.

ToughSat is really cool! However, it seems that the factoring2 mode has a bug. I have generated the cnf corresponding to 101 (which is prime) and minisat have found it satisfiable.

I have also a suggestion to simplify the CNF for factoring2. When factoring a n bits number, we can assume that one of the two factors will have a size less than |n/2| + 1 bits (enough to encode the square root of n). So it can be encoded with a multiplication of (|n/2| + 1) * n bits instead of a n*n bits as it is the case here (according to the comments about the factor’s encoding). This should significantly reduce the number of clauses and variables.

As far as I can tell, there are no known hard instances of GI. not even ones that were subsequently made easy. Cai-Fürer-Immerman gave examples that showed that one putative invariant was inadequate and the same technique later showed another to be inadequate. Miyazaki used the CFI technique to produce “medium” difficulty instances that show Mckay’s algorithm (nauty) to take exponential time, but which are bounded degree, and thus solved by Luks’s algorithm. My impression is that the best algorithm by worst-case complexity, Babai-Luks, is related to Luks, and thus it, too should classify these graphs quickly, but I’m not sure.

So, maybe CFI could produce examples that could stump BL, but that seems to be an open problem. I don’t think anyone has ever had to produce an algorithm to deal with a hard instance.

Also, there’s an asymmetry between positive and negative examples. If you (constructively) prove that a family of graphs are different, the method of proof yields an invariant, which you might expect to be computable in polynomial time, and thus you can add it to your algorithm to handle this family. But I believe Miyazaki’s medium instance is a positive instance, where nauty struggles to find the isomorphism. Thus it seems difficult to patch the algorithm to handle the example (though other examples handle it already). I’m not sure what conclusion to draw from this.

fagagr4bh,

wikipedia is correct, but leaves out a lot of detail about the procedure, especially what is being committed to.

However, even if it is not P but often easy the protocol seems broken. Is it the case that every graph has hard instances of GI? For instance, following Lipton’s recent post, if you knew that the graph of interest was free of a certain minor, could one solve the isomorphism quickly? Likewise, is it the case that one can generate a never ending stream of hard instances of GI, so you can request isomorphisms until you get an easy one?

The situation with factoring is completely different: as far as anyone knows, factoring a random n-bit integers is hard. So in particular, it’s very easy to generate hard instances of factoring, but very hard to generate hard instances of GI (as soon as you describe how you’re generating the graphs, someone can probably come up with a distinguishing criterion for non-isomorphic pairs).

Searching for this, I see you often invoke GI being easy in practice as evidence for its being in P. Does it seem any easier than factoring? Factoring a random number is easy, isn’t it? It’s just that we often like to make hard instances. I think there was a time when people didn’t know how to make hard pairs of graph, but now I think they do.

It seems weird to me to expect GI to be easier than factoring.

I think GI is probably in P, and it’s known to be in NP. (On the other hand, we also know that it can’t be NP-complete unless the polynomial hierarchy collapses.)