News for hackers. Stuff that matters.

A comment on Efficient algorithms, the Exponential Time Hypothesis, and losing the plot. Parent comment

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 ]