Hacker News

points by rbranson 3 days ago | 0 comments

The title buries the lede quite a bit:

> The Exponential Time Hypothesis is false

This is so far above my head it isn't even funny. I just looked up ETH and was 9 links in before I realized even the explanations of the parts of it were out of my grasp. Can someone explain the implications of this?

[–] kingstnap 3 days ago

It depends on your background. If you don't have a computer science background the statement needs layers and layers of buildup that can't happen in a single hacknews comment. But the outside implication is still accessible.

The outside implication for what is going on is that OpenAI has very clearly demonstrated insane capability in coming up with clever algorithms. You cannot deny some real level of super human like abstract reasoning here.

K-sat is the hard theoretical computer science problem. Nothing else is close in terms of how much it has been studied. There are journals and conferences for SAT.

It is really hard to come up with faster ways to solve it. So much so that people were convinced that you really can't go faster than exponential time. OpenAI has just shown a breakthrough construction better then decades of research by elite specialists was able to come up with.

[–] Sniffnoy 3 days ago

This is just one of the three ledes, really!

[–] eluru 3 days ago

sadly the only one they kind of explain, open AI is mysterious and cold like sasuke

[–] yu3zhou4 3 days ago

A newbie here, does it mean that SETH is false too?

[–] pavitheran 3 days ago

Yes it means both SETH and ETH are false.

[–] JonChesterfield 3 days ago

https://github.com/openai/math/blob/main/lean/docs/378.md

[–] JonChesterfield 3 days ago

by fucking sorry written at the end of the proof

[–] sebzim4500 3 days ago

They do that to make it easier for readers to verify the statement (which is entirely contained in that file) separately from the proof (which is spread over thousands of files and github can't even show them all).

Proof is at https://github.com/openai/math/tree/main/lean/OAI/Algorithms...

[–] mattr03 3 days ago

https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050...

looks like the real proof is in this file

[–] JonChesterfield 3 days ago

awesome, thanks!

[–] ollin 3 days ago

I was confused too, but it looks like https://github.com/openai/math/blob/main/lean/ComparatorChal... (with the sorry at the end) is just the problem statement; the actual proof is a big pile of lean in the Algorithms folder, with the final theorem stated here https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050...