I'm reading O(1.3289^n) for 3-colorability.

> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.

This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.

> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.

I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:

* Planar graph 3-colouring (P3COL) is NP-complete;

* Therefore 3-SAT can be reduced in polynomial time to P3COL;

* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;

* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).

That doesn't feel right ... where is the error?

Say the polynomial reduction is P(n)=n^2 then the algorithm for 3-SAT is 2^O(sqrt(P(n))) = 2^O(n)

Gotcha ... thank you.

Now I need to digest the implications of that, and I need to find the algorithm for P3COL.

I need a coffee ...