Efficient algorithms, the Exponential Time Hypothesis, and losing the plot

Re:Efficient algorithms, the Exponential Time Hypothesis, an... by ColinWright on Tuesday November 03, 2026 @09:16AM (#50352291)

> 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?

[ Parent | on HN ]

Re:Efficient algorithms, the Exponential Time Hypothesis, an... by dooglius on Tuesday November 03, 2026 @09:25AM (#50352382)

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

[ Parent | on HN ]

Re:Efficient algorithms, the Exponential Time Hypothesis, an... by ColinWright on Tuesday November 03, 2026 @09:33AM (#50352470)

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 ...

[ Parent | on HN ]