Comment by martinhath
12 hours ago
ETH is false! This is one of the big long-standing hypotheses that I actually remember from university, and afaik, it was reasonable to assume it would be true; reasonable enough for a lot of papers and results to assume this for bounds or hardness proofs of common problems in parameterized complexity, anyways.
Also glad to see that one of the authors of the paper stating it is also in the loop here.
2026 is weird.
What will happen to fine grained complexity if ETH is false? So there will be a solution for the Clique problem? So our social networks will evolve differently after this?
From what I understand, this proves mathematically that complex problems can be solved faster than we thought.
Now... the algorithm only works at impossible scales, so it changes (probably) absolutely nothing for real life or social networks.
Impossible scales in 2026 terms but what about 2076? Genuine question
1 reply →
What were the reasons to assume it would be true? I mean if you assume that NP < EXPTIME (which seems very likely) then you end up with algorithms that run in exponential time, but can't simulate turing machines with polynomial overhead. Obviously you can't simulate TMs with just anything, but most of the time... computation finds a way?