News for hackers. Stuff that matters.

A comment on Efficient algorithms, the Exponential Time Hypothesis, and losing the plot.

Re:Efficient algorithms, the Exponential Time Hypothesis, an... by emil-lp on Tuesday November 03, 2026 @06:43AM (#50350779)
About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.

It is almost the same as ETH, but allows for non-polynomial improvements in the exponent (which is what was proved by Clause/ChatGpt).

Recommended reading: https://arxiv.org/abs/2611.02650

[ Parent | on HN ]
Re:Efficient algorithms, the Exponential Time Hypothesis, an... by aleph_minus_one on Tuesday November 03, 2026 @08:29AM (#50351743)
> About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.

In 3 months: some AI frontier lab will disprove SH.

[ Parent | on HN ]