News for hackers. Stuff that matters.
Re:A look at OpenAI’s math that’s claimed computes faster Fo... by AnotherGoodName on Tuesday October 13, 2026 @12:25AM (#50066713)
It’s unintentionally making a mockery of OpenAIs results by highlighting Blums speedup theorem in action. Namely that you can always reduce time complexity with a small move into space complexity.

That unintentional mockery of a repo is 262million lines of such moves and growing. I don’t think for a second anyone involved has a clue about complexity theory though or they’d just jump to the obvious “O(1) time complexity using an O(2^n) lookup table to cover all possible n bits of input” which is the final end state of Blums speedup theorem.

Re:A look at OpenAI’s math that’s claimed computes faster Fo... by ashdksnndck on Tuesday October 13, 2026 @04:07AM (#50068312)
The input is unlimited size and the algorithm is achieving a speedup with constant size code.
Re:A look at OpenAI’s math that’s claimed computes faster Fo... by AnotherGoodName on Tuesday October 13, 2026 @09:46AM (#50071703)
The above 2^n is just the extreme. There’s always baby steps to that direction. If you want you can point an agent at any known nlogn algorithm (eg. Sorting) and quickly get similar improvements in a similar way. We’re about to see an explosion of ‘complexity bound of x broken!’ as people discover what the creator of complexity theory warned us about. Namely that there’s never hard limits in complexity theory and you can always speed up any time complexity with a cost in space complexity. There never was some impassable nlogn boundary for any algorithm.