Hacker News
points by abetusk 3 days ago | 0 comments
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...

[–] debo_ 3 days 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.
[–] slashtrends 3 days ago
They gave the algorithm to the original authors of the papers to review, I bet their reaction was similar to yours.
[–] danbruc 2 days 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.
[–] a115ltd 2 days ago
Knowing the count also gives you a O(n) way of finding a solution.
[–] dragontamer 2 days ago
No.

The number of valid permutations of 10 things is 10!. Reviewing all 10! Things is clearly exponential or even worse than exponential.

We can get the count of 10! pretty easily, far easier than trying all combinations manually.

[–] danbruc 2 days ago
The parent comment is correct, if you can count the solutions, it is easy to find a solution. Assuming there is a solution, you set the first variable to either true or false and then count the solutions. If it is zero, you made the wrong choice and the first variable must be set to the opposite value. Repeat for the remaining variables until you have fixed all of them and found a solution. This takes n invocations of the counting algorithm and is probably what the parent comment means with O(n) even though this is not correct as it is O(n times whatever the counting algorithm runtime is) and not just O(n).

But the parent comment also missed my point. They have an algorithm for the counting problem which also provides a subexponential algorithm for the decision and search problem. But they could have refuted the exponential time hypothesis with a subexponential search or decisions algorithm which would not [easily] provide a subexponential counting algorithm.

[–] hn_throwaway_99 2 days ago
For folks who believe that LLM-based AI only operates with the "convex hull" of its training data, I'm curious how they interpret this result.

To summarize, a lot has been discussed recently about whether LLMs are just really, really good at finding connections between existing information (i.e. the world's smartest and best search engine), or whether they are capable of discovering truly unique, novel ideas. Because many of the very impressive recent AI math results were often just tying together ideas and theories that were already known (and I don't mean to minimize those accomplishments), it was surmised (and, just speaking for myself, hoped) that LLMs operated within this "convex hull", and thus there would always be at least some axis where LLM-based AI wouldn't surpass humans.

Now, this idea of the convex hull of training data is not very clearly defined, and people can and have argued about what it means. But in this case, OpenAI disproved a conjecture that was widely assumed to be true. This was a genuinely surprising result that many experts were shocked by. I'm not a mathematician so I'm not qualified to determine if this was a "truly unique" realization, but a really surprising result seems like it would be a candidate for AI solving a problem in a manner "outside the convex hull".

[–] impossiblefork 2 days 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.
[–] casey2 3 days 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 3 days 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.

[–] vaylian 2 days ago
How about AI solves climate change next? That's an important open problem.
[–] jatora 2 days ago
Climate change has many clean solutions lol. Just none that anyone gives a fuck about enacting. We'll deal with it post singularity (if we even care then)
[–] vaylian 2 days ago
Then the open question simply becomes how to make humans give a fuck.
[–] rocqua 2 days ago
It's not the type of problem where a useful solution can be verified in Lean. Which makes LLMs a lot less good at solving that type of problem.
[–] theresq 2 days ago
One possible path is human extinction. I guess with current alignment problems, it may be the chosen path. :|
[–] Cub3 2 days ago
You forgot to add "make no mistakes"
[–] sylware 2 days ago
microsoft "open"AI is... open source?

really...

You meant deepseek?