What is ludicrously hard for not that much larger of a problem size is problems of the form ‘of this assignment to all variables, at least half plus one must be correct’. Anything davis-putnam based falls over laughably on those problems. However, there is a trick which I suspect works: generate a random assignment, use linear programming to find the minimum sum of that assignment, then round up to generate a new restriction (because the sum of a bunch of values which all all 0 or 1 which must be 2.4 must of course be 3) and then throw that back into the pool of restrictions. Repeat until rounding off one of the minima yields a real solution, or you have enough restrictions to show the problem is insoluble.

This technique superficially appears similar to the thing whose name I forget which uses the same round-up technique to prove things insoluble, but it’s actually quite different in that it’s being used randomly and doesn’t guarantee termination. I suspect that it works quite efficiently on problems which are otherwise completely intractable.

I’d test it myself if I could get a linear programming package which works (and yes, I’ve tried, several times).

Anyhow, what I know for a fact is that the problem of knot classification is still open, and that it’s intimately linked with the problem of 3-manifold classification, because the inverse space of a knot forms a 3-manifold, and at some point around 1990 or so it was shown that if two knots have the same manifold then they’re the same knot (but that isn’t true of links).

The possible link to perelman’s work is that articles I read on knots said that the big problem with classification was proving the poincare conjecture. Of course, it’s entirely possible that this was speculative wishful thinking, that it sure seemed like a first step in the direction of classification was to be able to prove poincare, but there wasn’t a formal argument about why that should help.

Intuitively, given the vague descriptions of perelman’s work which I’ve read, it seems possible that one could take any old manifold and reduce its ricci flow as much as possible, with some kind of surgery thrown in there, and in the end have a very nice algorithm for canonicalization, which could then be used for comparison. Keep in mind, of course, that I have no idea what I’m talking about here.

Oddly, web searching for knot classification turns up a bunch of nut job web sites, of people who don’t understand the difference between writing a program to compare knots using a combination of classification techniques, and conjecturing that the combination of those techniques never turns up any false positives.

By the way, an interesting computational complexity result related to a proof of a long-standing theorem (and I’m really just saying this to contribute an actual fact to this thread, not because it has anything to do with the topic at hand) is that the old ‘proof’ of the 4-color theorem (the one which was never actually proven) yielded a quartic time algorithm for finding a coloring, while the newer (and thoroughly accepted) proof yields a quadratic time algorithm. It seems not inconceivable that a linear time algorithm would be found, possibly without even sustantially reworking the proof, since it wasn’t really designed with optimizing for asymptotic runtime.

You can always start with hard instances of your favorite NP problem and then reduce. But you’re right that (particularly because of survey propagation) random 3SAT doesn’t seem nearly as hard as previously thought. Interestingly, random k-SAT for k>>3 seems much harder; apparently survey propagation fails badly on it.

Graph isomorphism, on the other hand, seems to have no hard instances at all, which makes one wonder, how can a problem be hard if it has no hard instances?

Indeed, for exactly that reason, many people conjecture that GI is in P.

Bram: We know there’s an algorithm for unknotting; Haken proved that in 1961. Indeed, we know it’s in AM intersect coAM. The question is whether it’s in P. I’d be astonished if Perelman’s work had anything to say about that, so do let me know if you find a reference.

Graph isomorphism, on the other hand, seems to have no hard instances at all, which makes one wonder, how can a problem be hard if it has no hard instances?