News for hackers. Stuff that matters.

ColinWright

ColinWright on Hacker News

Re:Efficient algorithms, the Exponential Time Hypothesis, and losing t... 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 ...

Re:Efficient algorithms, the Exponential Time Hypothesis, and losing t... 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?

Re:Patrick Stewart has died on Friday October 30, 2026 @04:07AM (#50301032)
Ah.

Thank you.

Re:Patrick Stewart has died on Thursday October 29, 2026 @06:37PM (#50297220)
He was in Oblivion? The film with Tom Cruise?

I've found no evidence of this ... can you confirm?

Re:CVE-2026-111943: Compromised Intermediate Certificate Authority on Thursday October 22, 2026 @05:16AM (#50193086)
Up for me, but slow to load.
Re:A Visual Intro to Complex Numbers on Tuesday October 13, 2026 @12:18PM (#50074171)
Wait ... you think of the Reals as converging infinite series?

I think of them as pairs (L,R) of sets of rationals, with every in L less than or equal to every thing in R ...

Re:Why OpenAI's latest results dump has left mathematicians in shock on Saturday October 10, 2026 @07:08PM (#50038058)
Quoting from TFA:

> A senior colleague of mine found one of his favourite problems among those solved and attempted to read the accompanying paper. He told me it was so unintelligible that, had he received it as an editor at a mathematics journal, “it would have gone straight into the bin”.

Older »