alt Hacker NewsThere is a difference between one-off results and processes that can generate new results at an industrial scale.
Conditional lower bounds are a way of building understanding of the essential difficulty of specific computational problems. But if AI can now routinely generate marginal improvements, conditional bounds based on unproven assumptions become a waste of effort.
This is mostly due to how mathematics works. Ideally, we would like to prove something like "if problem A is essentially this difficult, problem B is essentially that difficult". But what we actually prove is more like "if (specific formulation of the difficulty of problem A), then (specific formulation of the difficulty of problem B)".
But those specific formulations become fixed targets for the AI to attack. If it manages to break the specific assumption, for example by creating an O(n^1.9998) time algorithm that is for all intents and purposes worse than a naive O(n^2) time algorithm, the conditional result becomes void. We could try to salvage the result with a different formulation, but that again becomes a fixed target.
This is essentially Goodhart's Law. We measure improvement with highly precise metrics, while we are actually interested in qualitative understanding.
EDIT: If theorems and proofs become cheap, marginal improvements are no longer interesting. Qualitatively better algorithms or unconditional lower bounds would be actual contributions. As would be a specific formulation of a conditional result that is robust against technical improvements made by AI targeting that specific formulation.
Replies
it just means that the assumptions we are making in the first place is wrong? nothing here is a dead-end because essentially we are at the same place before. people might even go ahead and say now if it's n^1.5 what happens, what results can be true.
i feel like you are arguing there is -- even in the narrow utility of PROOFS -- there is a goodness in being an ostrich with its head in the sand. If that's true, people can still be that ostrich and pretend the bound is now n^1.9 or something.
> There is a difference between one-off results and processes that can generate new results at an industrial scale.
This is the part of your reply that I find the most compelling. If such results can be produced "cheaply", then yes, it becomes less interesting for humans to devote their own time and energy to pursuing them. But while that would be bad news for mathematicians, I don't hold that to be a negative thing on its face. (I'm not sure that you do either, but it's a commonly held view and consistent with your words so far.) Fundamentally, that's because I don't think mathematicians have a right to do mathematics research for a living any more than buggy whip manufacturers have a right to make buggy whips for a living.
On the (to my mind, secondary) question of whether "small"/"technical" advances in algorithms will now become cheap: I don't think this will happen in any case. Unlike most applications of Goodhart's Law, which involve exploiting something trivial like line counts or git commits, I think improving a well-known problem's asymptotic complexity is sufficiently "meaty" that it will never be cheaply automated. Even if some theorem is discovered in future that "automates" optimal algorithm creation for a wide range of problems (imagine something like a turbocharged Courcelle's Theorem), I'm certain there will always be problems for which we don't know the answer.