Still, the result is very interesting, since many problems can be solved asymptotically faster once subproblems that can be represented as 3-SAT can be solved faster. 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.
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?
Now I need to digest the implications of that, and I need to find the algorithm for P3COL.
I need a coffee ...
I might be misunderstanding you, but this surely depends on the size of the candidate set in the problem. For a problem like "determine whether a given list of integers of length `n` contains a pair that sum to 100" the naive brute-force algorithm is polynomial. If you replace "pair" by "subset" then the naive brute-force algorithm becomes exponential.
The question can actually be generalized further - is it the case that for any solvable problem it's possible to find a solution without verifying every possible solution, and more specifically, only a tiny subset of the solution space? This would apply even beyond P vs NP, the same question would arise for EXP vs NEXP (that is, problems where we can find a solution vs just verify a given solution in exponential time), and same for factorial or Ackerman or any other complexity we want to imagine.
Looking at the problem in this way should also make it easier to construct a more strictly practical version of P vs NP, though it actually gets much harder to pin down details. That is, we can construct complexity classes that better match "what is plausibly solvable with a real computer" vs "what is plausibly verifiable with a real computer" and ask a similar question: given any problem of the second kind, can there be any generic algorithm of the first kind that would solve it?
Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not". Polynomial complexity is what you get when the problem itself has some kind of structure that you can exploit to either directly construct a solution, or to generate a very small set (relative to the problem size) of possible solutions that have to be checked by hand.
Now, it is true that for all practical problem-solving purposes, "P = NP but only with algorithms that require n^10^80 or more time (with this as a proven lower bound for even the typical case, no hope of improving)" would be exactly equivalent to "P != NP". However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions. And it could still open the door to finding new sub-classes of actually easy instances of these problems that are not known today, even if the worse case remains just as intractable.
Now, note the refutation of ETH with the new algorithm found by AI is not really that impressive, it doesn't seem to have that deep of an implication. Sub-exponential running times are not that fundamentally different from exponential ones - they basically just tell you that the problem has just enough structure to eliminate a certain class of possible solutions outright, instead of spending the time to actually verify them. If the algorithm found had been polynomial, even of a huge degree, this would have been a completely different discussion. As it is, we'll just replace the ETH with a "nearly-E"TH and nothing much changes.