pajenegod's blog

By pajenegod, history, 44 minutes ago, In English

This is crazy.

People used to think that 3SUM couldn't be solved in O(n^1.99999), but couple of weeks ago that conjecture was disproven by Anthropic's AI. They also disproved some related conjectures to other similar problems, but importantly they didn't disprove the Exponential Time Hypothesis (ETH). The conjecture states that no subexponential algorithm for 3SAT exists.

Today, ETH was disproven by openAI. See also this.

There is (was) an entire field of research, called fine grained complexity, that fundamentally is built on these these conjectures. This means that in half a month, an entire field of theoretical computer science has completely collapsed. This has been a funeral for an entire field of science.

The entire reason 3SUM was interesting was because people thought this conjecture to be true. With the conjeture being false, any research that assumed it is basically worthless. People were never interested in finding an algorithm for 3SUM. They just hoped there wasn't one.

A new algorithm for 3SAT is definitely interesting in its own right. But this is not the outcome that anyone had wished for.

Who knows, maybe $$$P = NP$$$.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
43 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pajenegod (previous revision, new revision, compare).

»
41 minute(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pajenegod (previous revision, new revision, compare).

»
40 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pajenegod (previous revision, new revision, compare).