Comment by abetusk

11 hours ago

ETH is false! I really would not have believed it.

[0]:

> We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula. For every fixed k ⩾ 2, on a formula with n variables and m clauses, our algorithm uses $poly_k (n, m)$ space and runs in time $(n + m)^{O_k(1)} 2^{n/(\log n)^{1/2 + o(1)}}$

The dominant term there is (roughly) $2^{n / (\log n)^{0.5}}$, so still superpolynomial but less than exponential. Fucking wild.

[0] https://github.com/openai/math/blob/main/preprints/The-Expon...

9 comments

abetusk

Reply
impossiblefork  1 hour ago

I never believed the EHT, but I can't prove I didn't and I only didn't believe it for the shallow reason that I didn't feel that there was a strong argument that it should actually be exponential, since there are so many almost-exponential things that it could equally well be.

slashtrends  10 hours ago

They gave the algorithm to the original authors of the papers to review, I bet their reaction was similar to yours.

danbruc  2 hours ago

And the claimed algorithm solves the counting problem, i.e. determining the number of different solutions, which in many cases is much harder than just determining whether a solution exists or finding one of the solutions.

debo_  10 hours ago

Yeah, this really blew me away. I took a graduate computational complexity course and the original prof had to drop out due to health reasons. We got another professor from a completely different field who was basically as green in the field as we were, but with far better research chops. It turned the course into kind of a long-running lab where we just kind of did whatever we wanted. We spent a lot of time just philosophizing (mostly uselessly) about the ETH. I am very chuffed to see this result.

casey2  5 hours ago

And who says AI doesn't create open problems. This unlocks thousands of high quality open problems.

Turns out the 'opne' in open AI wasn't referring to open source, but open problems!

  • contubernio  4 hours ago

    It's not AI that has created those open problems. It has simply shown that some conjecture is false and that leads naturally to problems in a sense already posed.

    A very different thing is proposing a framework and in it identifying interesting questions. So far AI has only worked within existing frameworks addressing problems already posed. That may change in the future, but it would be a genuine and qualitative evolution.