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?
replyWhat 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?
replyFrom what I understand, this proves mathematically that complex problems can be solved faster than we thought.
replyNow... 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
reply