Comment by ComplexSystems
17 hours ago
This is a very loaded blog post. A unit-cost RAM is a fairly standard model of computation when working with algorithms. When we say that comparison sorting of strings takes O(n log n) time, for instance, we are also implicitly assuming a unit cost for comparing two strings. In real life, comparing two strings scales linearly with string length. Maybe that's silly, but it's par for the course. The original FFT is also assuming unit cost multiplication when we say it is O(n log n) time - we mean O(n log n) multiplies.
Similarly, yes, it's a galactic algorithm, but these things are still viewed as meaningful. The fact that it is even possible at all with a unit cost RAM asymptotically is an incredible result that nobody expected.
The string comparison model is useful in the regime where string lengths are much shorter than list lengths and can be bounded by a constant. It would be a horribly broken (i.e. unrepresentative) model if you were constructing intermediate strings whose lengths could grow arbitrarily and become much longer than list lengths.
One can of course make a puzzle out of anything, but it behooves asking what situation is being modelled by that problem.
And yes, this criticism might apply more broadly to TCS rather than just this specific artifact from OpenAI. It's reward hacking regardless of whether humans do it or LLMs.
Have we settled on a really good universal approximation model of memory+computation or is this a hard topic to solve in itself ?