Comment

Comment by jltsiren

There 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.

parent jltsiren 25 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton